NDLI: Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Please wait, while we are loading the content...

Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error

The streaming complexity of cycle counting, sorting by reversals, and other problems

Streaming k-means on well-clusterable data

Efficient sketches for the set query problem

Exponential time improvement for min-wise based algorithms

A simple and fast 2-approximation algorithm for the one-warehouse multi-retailers problem

Generalized machine activation problems

An online scalable algorithm for minimizing $l_{k}-norms$ of weighted flow time on unrelated machines

Online scalable scheduling for the $l_{k}-norms$ of flow time without conservation of work

Online scheduling on identical machines using SRPT

A complete resolution of the Keller maximum clique problem

On independent sets in random graphs

Coloring random graphs online without creating monochromatic subgraphs

The maximum size of a Sidon set contained in a sparse random set of integers

On Buffon machines and numbers

Graph coloring via the probabilistic method

An almost optimal unrestricted fast Johnson-Lindenstrauss transform

A Stackelberg strategy for routing flow over time

A subexponential lower bound for the random facet algorithm for parity games

On minmax theorems for multiplayer games

Near-optimal no-regret algorithms for zero-sum games

Local smoothness and the price of anarchy in atomic splittable congestion games

I/O-efficient contour queries on terrains

Implicit flow routing on terrains with applications to surface networks and drainage structures

Shortest non-crossing walks in the plane

Computing shortest paths amid pseudodisks

On the complexity of time-dependent shortest paths

A master theorem for discrete divide and conquer recurrences

Optimal pattern matching in LZW compressed strings

Random access to grammar-compressed strings

Ordered and unordered top-K range reporting in large data sets

Top-K color queries for document retrieval

Mobile geometric graphs: detection, coverage and percolation

Randomized diffusion for indivisible loads

Fast information spreading in graphs with large weak conductance

On the randomness requirements of rumor spreading

Rumor spreading and vertex expansion on regular graphs

Bin packing via discrepancy of permutations

Algorithms and hardness for subspace approximation

Approximating matrix p-norms

Subsampling mathematical relaxations and average-case complexity

Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition

Faster quantum algorithm for evaluating game trees

Reflections for quantum query algorithms

Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D

The power of nondeterminism in self-assembly

Algorithms for implicit hitting set problems

An algorithmic decomposition of claw-free graphs leading to an $O(n^{3})-algorithm$ for the weighted stable set problem

Randomized greedy: new variants of some classic approximation algorithms

Randomized variants of Johnson's algorithm for MAX SAT

The local lemma is tight for SAT

Pricing on paths: a PTAS for the highway problem

On the approximability of budget feasible mechanisms

Welfare guarantees for combinatorial auctions with item bidding

Mechanism design via correlation gap

Bayesian incentive compatibility via fractional assignments

Bayesian incentive compatibility via matchings

Bidimensionality and EPTAS

Slightly superexponential parameterized problems

Known algorithms on graphs of bounded treewidth are probably optimal

Continuous local search

Range selection and median: tight cell probe lower bounds and adaptive data structures

Where computer vision needs help from computer science

An optimal-time construction of sparse Euclidean spanners with tiny diameter

Fast, precise and dynamic distance queries

Approximate nearest neighbor search for low dimensional queries

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound

A nonlinear approach to dimension reduction

Hitting time results for Maker-Breaker games: extended abstract

Packing tight Hamilton cycles in 3-uniform hypergraphs

Networks of random cycles

Phase transition for Glauber dynamics for independent sets on regular trees

On belief propagation guided decimation for random k-SAT

The asymmetric traveling salesman problem on graphs with bounded genus

Capacitated Metric Labeling

Multicommodity facility location under group Steiner access cost

Survivable network design problems in wireless networks

Prize-collecting Steiner problems on planar graphs

On graph crossing number and edge planarization

Ranking with submodular valuations

Multi-budgeted matchings and matroid intersection via dependent rounding

Submodular maximization by simulated annealing

The matroid median problem

Persistent predecessor search and orthogonal point location on the word RAM

New approximation algorithms for minimum enclosing convex shapes

Computing the independence number of intersection graphs

Minimum cuts and shortest non-separating cycles via homology covers

Embedding stacked polytopes on a polynomial-size grid

Overlap properties of geometric expanders: extended abstract

On the degree distribution of random planar graphs

Component structure of the vacant set induced by a random walk on a random graph

The multiple-orientability thresholds for random hypergraphs

The rigidity transition in random graphs

Online vertex-weighted bipartite matching and single-bid budgeted allocations

Secretary problems: laminar matroid and interval scheduling

Matroid secretary problem in the random assignment model

Online stochastic matching: online actions based on offline statistics

An optimal lower bound for buffer management in multi-queue switches

An intersection model for multitolerance graphs: efficient algorithms and hierarchy

Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification

Faster replacement paths

Computing replacement paths in surface embedded graphs

Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Algebraic algorithms for linear matroid parity problems

On parity check (0, 1)-matrix over $Z_{p}$

Code equivalence and group isomorphism

Efficient algorithms for some special cases of the polynomial equivalence problem

Low rank matrix-valued chernoff bounds and approximate matrix multiplication

Computational geometry for non-geometers: recent developments on some classical problems

Improved deterministic algorithms for decremental transitive closure and strongly connected components

Approximating the girth

Approximating the statistics of various properties in randomly weighted graphs

Counting and detecting small subgraphs via equations and matrix multiplication

On succinct convex greedy drawing of 3-connected plane graphs

Distributed selfish load balancing on networks

On the complexity of approximating a Nash equilibrium

Fast convergence of natural bargaining dynamics in exchange networks

Wireless capacity with oblivious power in general metrics

A constant-factor approximation for wireless capacity maximization with power control in the SINR model

On LP-based approximability for strict CSPs

Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set

Hardness results for agnostically learning low-degree polynomial threshold functions

Tight hardness results for minimizing discrepancy

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions

Improved approximation results for stochastic knapsack problems

The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem

Approximate dynamic programming using halfspace queries and multiscale Monge decomposition

Nearly tight bounds for testing function isomorphism

The dichotomy of list homomorphisms for digraphs

Dichotomy for Holant problems of Boolean domain

Bounding the randomized decision tree complexity of read-once Boolean functions

Improved space bounds for cache-oblivious range reporting

Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent

Improved bound for the union of fat triangles

Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Content Provider	ACM Digital Library
Author	Bernstein, Aaron Roditty, Liam
Abstract	We present the first dynamic shortest paths algorithms that make any progress beyond a long-standing O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas). • Given a source s, we present an algorithm that maintains (1 + ε)-approximate shortest paths from s with an expected total update time of Õ(n2+O(1/√log n)) over all deletions (so the amortized time is about $Õ(n^{2}/m)).$ The worst-case query time is constant. The best previous result goes back three decades to Even and Shiloach [16] and Dinitz [12]. They show how to decrementally maintain an exact shortest path tree with a total update time of O(mn) (amortized update time O(n)). Roditty and Zwick [22] have shown that O(mn) is actually optimal for exact paths (barring a better combinatorial algorithm for boolean matrix multiplication), unless we are willing to settle for a Ω(n) query time. In fact, until now, even approximate dynamic algorithms were not able to go beyond O(mn). • For any fixed integer k ≥ 2, we present an algorithm that decrementally maintains a distance oracle (for all pairs shortest distances) with a total expected update time of Õ(n2+1/k+O(1/√log n)) (amortized update time about $Õ(n^{2+1/k}/m).$ The space requirement is only O(m + $n^{1+1/k}),$ the stretch of the returned distances is at most 2k ™ 1 + ε, and the worst-case query time is O(1). The best previous result of Roditty and Zwick [21] had a total update time of Õ(mn) and a stretch of 2k ™ 1. Note that our algorithm implicitly solves the decremental all-pairs shortest path problem with the same bounds; the best previous approximation algorithm of Roditty and Zwick [21] returned (1 + ε) approximate distances, but used $O(n^{2})$ space, and required Õ(mn) total update time. As with the previous problem, our algorithm is the first to make progress beyond the O(mn) total update time barrier while maintaining a small query time. We present a general framework for accelerating decremental algorithms. In particular, our main idea is to run existing decremental algorithms on a sparse subgraph (such as a spanner or emulator) of the graph rather than on the original graph G. Although this is a common approach for static approximate shortest-path problems, it has never been used in a decremental setting because maintaining the subgraph H as edges are being deleted from G might require inserting edges into H, thus ruining the "decrementality" of the setting. We overcome this by presenting an emulator whose maintenance only requires a limited number of well-behaved insertions. In other words, we present a general technique for running decremental algorithms on a sparse subgraph of the graph. Once our framework is in place, applying it to any particular decremental algorithm only requires trivial modifications; most of the work consists of showing that these algorithms as they are still work in our restricted fully dynamic setting, where we encounter not just arbitrary deletions (as in the original setting), but also restricted insertions.
Starting Page	1355
Ending Page	1365
Page Count	11
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-23
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in