NDLI: Improved algorithms for fully dynamic geometric spanners and geometric routing

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

Fast dimension reduction using Rademacher series on dual BCH codes

Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections

A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods

Explicit constructions for compressed sensing of sparse signals

Improved distance sensitivity oracles via random sampling

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Holographic algorithms with unsymmetric signatures

The UGC hardness threshold of the $ℓ_{p}$ Grothendieck problem

Succinct approximate convex pareto curves

Efficient reductions among lattice problems

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

Greedy drawings of triangulations

Maintaining deforming surface meshes

Exact and efficient 2D-arrangements of arbitrary algebraic curves

On properties of random dissections and triangulations

Graph algorithms for biological systems analysis

Adaptive local ratio

Two-phase greedy algorithms for some classes of combinatorial linear programs

Analysis of greedy approximations with nonsubmodular potential functions

Yet another algorithm for dense max cut: go greedy

Computing large matchings fast

A fractional model of the border gateway protocol (BGP)

Minimizing average latency in oblivious routing

Distributed broadcast in unknown radio networks

The power of memory in randomized broadcasting

Competitive queue management for latency sensitive packets

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Product growth and mixing in finite groups

Concatenated codes can achieve list-decoding capacity

Noisy sorting without resampling

Algorithms for the coalitional manipulation problem

On allocations that maximize fairness

On the value of coordination in network design

Auctions for structured procurement

Fast load balancing via bounded best response

(Almost) optimal coordination mechanisms for unrelated machine scheduling

Ultra-low-dimensional embeddings for doubling metrics

Earth mover distance over high-dimensional spaces

Almost Euclidean subspaces of $ℓ^{N}_{1}$ via expander codes

Embedding metric spaces in their intrinsic dimension

Optimal universal graphs with deterministic embedding

Fast and reliable reconstruction of phylogenetic trees with very short edges

Trace reconstruction with constant deletion probability and related results

Improved string reconstruction over insertion-deletion channels

Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly

Approximating general metric distances between a pattern and a text

A near-linear time algorithm for computing replacement paths in planar directed graphs

Bounded-leg distance and reachability oracles

A nearly linear time algorithm for the half integral disjoint paths packing

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

Broadcast scheduling: algorithms and complexity

Graph balancing: a special case of scheduling unrelated parallel machines

Non-clairvoyant scheduling with precedence constraints

Provably good multicore cache performance for divide-and-conquer algorithms

Balls and bins with structure: balanced allocations on hypergraphs

Arc-disjoint in-trees in directed graphs

Finding one tight cycle

Set connectivity problems in undirected graphs and the directed Steiner network problem

Matroid intersection, pointer chasing, and Young's seminormal representation of $S_{n}$

Iterated rounding algorithms for the smallest k-edge connected spanning subgraph

Shuffling cards, adding numbers, and symmetric functions

On the bichromatic k-set problem

Geodesic Delaunay triangulation and witness complex in the plane

Minimum weight convex Steiner partitions

Improved algorithms for fully dynamic geometric spanners and geometric routing

On the connectivity of dynamic random geometric graphs

Improved algorithmic versions of the Lovász Local Lemma

L(2,1)-labelling of graphs

Catalan structures and dynamic programming in H-minor-free graphs

Computing excluded minors

An algorithm for improving graph partitions

Improved algorithms for orienteering and related problems

Approximation algorithms for labeling hierarchical taxonomies

Fast approximation of the permanent for very dense problems

Approximating TSP on metrics with bounded global growth

Fully polynomial time approximation schemes for stochastic dynamic programs

On distributing symmetric streaming computations

Tight lower bounds for selection in randomly ordered streams

On distance to monotonicity and longest increasing subsequence of a data stream

Declaring independence via the sketching of sketches

Why simple hash functions work: exploiting the entropy in a data stream

Maximum overhang

Deterministic random walks on regular trees

Quasirandom rumor spreading

Universality of random graphs

The effect of induced subgraphs on quasi-randomness

Clustering for metric and non-metric distance measures

Metric clustering via consistent labeling

On clustering to minimize the sum of radii

A constant factor approximation algorithm for k-median clustering with outliers

Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension

The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond

Designing networks with good equilibria

Ascending auctions for integral (poly)matroids with concave nondecreasing separable values

Fast algorithms for finding proper strategies in game trees

Incentive compatible regression learning

Space-efficient dynamic orthogonal point location, segment intersection, and range reporting

In-place 2-d nearest neighbor search

Distribution-sensitive point location in convex subdivisions

Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

Sampling algorithms and coresets for $ℓ_{p}$ regression

Stochastic analyses for online combinatorial optimization problems

Online make-to-order joint replenishment model: primal dual competitive algorithms

Parallel monotonicity reconstruction

Better bounds for online load balancing on unrelated machines

Online budgeted matching in random input models with applications to Adwords

Computational advertising

Linked decompositions of networks and the power of choice in Polya urns

A local algorithm for finding dense subgraphs

PageRank and the random surfer model

Charity auctions on social networks

On the approximability of influence in social networks

Fast asynchronous byzantine agreement and leader election with full information

Unconditionally reliable message transmission in directed networks

A tight lower bound for parity in noisy communication networks

Ranged hash functions and the price of churn

Algorithms for distributed functional monitoring

Real-time indexing over fixed finite alphabets

Finding an optimal tree searching strategy in linear time

Dynamic optimality for skip lists and B-trees

Splay trees, Davenport-Schinzel sequences, and the deque conjecture

Fully dynamic algorithm for graph spanners with poly-logarithmic update time

SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems

Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities

Lower-bounded facility location

A plant location guide for the unsure

Approximating connected facility location problems via random facility sampling and core detouring

The hiring problem and Lake Wobegon strategies

Weak ε-nets and interval chains

Robust cost colorings

Comparing the strength of query types in property testing: the case of testing k-colorability

Sampling stable marriages: why spouse-swapping won't work

On stars and Steiner stars

Cutting cycles of rods in space: hardness and approximation

Empty-ellipse graphs

Recognizing partial cubes in quadratic time

Approximating geometric coverage problems

Improved algorithms for fully dynamic geometric spanners and geometric routing

Content Provider	ACM Digital Library
Author	Gottlieb, Lee-Ad Roditty, Liam
Abstract	For a set S of points in $ℝ^{d},$ a t-spanner is a sparse graph on the points of S such that between any pair of points there is a path in the spanner whose total length is at most t times the Euclidean distance between the points. In this paper, we show how to construct a (1 + ε)-spanner with $O(n/ε^{d})$ edges and maximum degree $O(1/ε^{d})$ in time O(n log n). A spanner with similar properties was previously presented in [6, 8]. However, using our new construction (coupled with several other innovations) we obtain new results for two fundamental problems for constant doubling dimension metrics: The first result is an essentially optimal compact routing scheme. In particular, we show how to perform routing with a stretch of 1 + ∈, where the label size is [log n] and the size of the table stored at each point is only O(log $n/ε^{d}).$ This routing problem was first considered by Peleg and Hassin [11], who presented a routing scheme in the plane. Later, Chan et al. [6] and Abraham et al. [1] considered this problem for doubling dimension metric spaces. Abraham et al. [1] were the first to present a (1 + ∈) routing scheme where the label size depends solely on the number of points. In their scheme labels are of size of [log n], and each point stores a table of size $O(log^{2}$ $n/ε^{d}).$ In our routing scheme, we achieve routing tables of size O(log $n/ε^{d}),$ which is essentially the same size as a label (up to the factor of $1/ε^{d}).$ The second and main result of this paper is the first fully dynamic geometric spanner with poly-logarithmic update time for both insertions and deletions. We present an algorithm that allows points to be inserted into and deleted from S with an amortized update time of $O(log^{3}$ n).
Starting Page	591
Ending Page	600
Page Count	10
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-01-20
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