NDLI: Improved approximation algorithms for the minimum latency problem via prize-collecting strolls

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

On the optimality of spiral search

An improved competitive algorithm for reordering buffer management

How to meet asynchronously (almost) everywhere

A 1.43-competitive online graph edge coloring algorithm in the random order arrival model

Towards the randomized k-server conjecture: a primal-dual approach

Testing monotone continuous distributions on high-dimensional real cubes

Property testing and parameter testing for permutations

Near-optimal sublinear time algorithms for Ulam distance

Lower bounds for testing triangle-freeness in Boolean functions

Counting stars and other small subgraphs in sublinear time

Cell-probe lower bounds for succinct partial sums

On the cell probe complexity of dynamic membership

Fully-functional succinct trees

Data structures for range minimum queries in multidimensional arrays

Counting inversions, offline orthogonal range counting, and related problems

Differential privacy in new settings

Lower bounds for edit distance and product metrics via Poincaré-type inequalities

Genus and the geometry of the cut graph

Testing planarity of partially embedded graphs

Inapproximability for planar embedding problems

Towards a calculus for non-linear spectral gaps

A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics

PTAS for maximum weight independent set problem with random weights in bounded degree graphs

Belief propagation for min-cost network flow: convergence & correctness

Finding the Jaccard median

The focus of attention problem

Recognizing a totally odd $K_{4}-subdivision,$ parity 2-disjoint rooted paths and a parity cycle through specified elements

Decomposition, approximation, and coloring of odd-minor-free graphs

The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

On brambles, grid-like minors, and parameterized intractability of monadic second-order logic

An (almost) linear time algorithm for odd cycles transversal

An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem

A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing

Region growing for multi-route cuts

Asymmetric traveling salesman path and directed latency problems

Improved approximation algorithms for the minimum latency problem via prize-collecting strolls

Quantum algorithms for highly non-linear Boolean functions

Compact ancestry labeling schemes for XML trees

Generating a d-dimensional linear subspace efficiently

Algorithms for ray class groups and Hilbert class fields

A space-time tradeoff for permutation problems

Algorithmic lower bounds for problems parameterized by clique-width

Bidimensionality and kernels

Solving MAX-r-SAT above a tight lower bound

Inapproximability for VCG-based combinatorial auctions

Price of anarchy for greedy auctions

Incentive compatible budget elicitation in multi-unit auctions

Utilitarian mechanism design for multi-objective optimization

Pricing randomized allocations

Universal ε-approximators for integrals

Optimally reconstructing weighted graphs using queries

Online learning with queries

Coresets and sketches for high dimensional subspace approximation problems

Convergence, stability, and discrete approximation of Laplace spectra

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Fast SDP algorithms for constraint satisfaction problems

Probabilistic analysis of the semidefinite relaxation detector in digital communications

Correlation clustering with noisy input

A polynomial time approximation scheme for k-consensus clustering

Google's auction for TV ads

A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs

Solving the replacement paths problem for planar directed graphs in O(n log n) time

Bounding variance and expectation of longest path lengths in DAGs

Highway dimension, shortest paths, and provably efficient algorithms

Maximum flows and parametric shortest paths in planar graphs

On the equilibria of alternating move games

Monotonicity in bargaining networks

Sharp dichotomies for regret minimization in metric spaces

Solving simple stochastic tail games

One-counter Markov decision processes

On nonlinear forbidden 0-1 matrices: a refutation of a Füredi-Hajnal conjecture

An improved construction of progression-free sets

Geometric optimization and sums of algebraic functions

Approximating the crossing number of graphs embeddable in any orientable surface

How far can you reach?

A model of computation for MapReduce

Synchrony and asynchrony in neural networks

Distributed agreement with optimal communication complexity

How good is the Chord algorithm?

Deterministic algorithms for the Lovász Local Lemma

A deterministic truthful PTAS for scheduling related machines

A Fourier space algorithm for solving quadratic assignment problems

EDF-schedulability of synchronous periodic task systems is coNP-hard

Reconstructing approximate phylogenetic trees from quartet samples

Shape replication through self-assembly and RNase enzymes

On the possibility of faster SAT algorithms

Paired approximation problems and incompatible inapproximabilities

Correlation robust stochastic optimization

Approximability of robust network design

Differentially private combinatorial optimization

Efficiently decodable non-adaptive group testing

1-pass relative-error $L_{p}-sampling$ with applications

On the exact space complexity of sketching and streaming small norms

A locality-sensitive hash for real vectors

Lower bounds for sparse recovery

Flow-cut gaps for integer and fractional multiflows

A max-flow/min-cut algorithm for a class of wireless networks

Testing additive integrality gaps

Classified stable matching

Basis reduction and the complexity of branch-and-bound

Randomized Shellsort: a simple oblivious sorting algorithm

Data-specific analysis of string sorting

Fast distance multiplication of unit-Monge matrices

Regular expression matching with multi-strings and intervals

Road network reconstruction for organizing paths

The power of convex relaxation: the surprising stories of matrix completion and compressed sensing

An online scalable algorithm for average flow time in broadcast scheduling

Resource minimization for fire containment

Algorithms and complexity for periodic real-time scheduling

Energy efficient scheduling via partial shutdown

SRPT is 1.86-competitive for completion time scheduling

The rank of diluted random graphs

The scaling window for a random graph with a given degree sequence

Efficient broadcast on random geometric graphs

Speeding up random walks with neighborhood exploration

Vertices of degree k in random maps

Cache-oblivious dynamic dictionaries with update/query tradeoffs

Applications of forbidden 0-1 matrices to search tree and path compression-based data structures

Faster exponential time algorithms for the shortest vector problem

Streaming algorithms for extent problems in high dimensions

Deletion without rebalancing in balanced binary trees

On linear and semidefinite programming relaxations for hypergraph matching

Partition constrained covering of a symmetric crossing supermodular function by a graph

Tree embeddings for two-edge-connected network design

A constant factor approximation algorithm for generalized min-sum set cover

Self-improving algorithms for convex hulls

The forest hiding problem: an illumination problem for maximal disk packings

Terrain guarding is NP-hard

Hardness results for homology localization

Orthogonal ham-sandwich theorem in $R^{3}$

The (1 + β)-choice process and weighted balls-into-bins

Quasirandom load balancing

Thin partitions: isoperimetric inequalities and a sampling algorithm for star shaped bodies

Phase transition for the mixing time of the Glauber dynamics for coloring regular trees

Rumour spreading and graph conductance

Improved approximation algorithms for the minimum latency problem via prize-collecting strolls

Content Provider	ACM Digital Library
Author	Blasiak, Anna Archer, Aaron
Abstract	The minimum latency problem (MLP) is a well-studied variant of the traveling salesman problem (TSP). In the MLP, the server's goal is to minimize the average latency that the clients experience prior to being served, rather than the total latency experienced by the server (as in the TSP). The MLP sometimes goes by other names, such as the traveling repairman problem, or the deliveryman problem. Unlike most combinatorial optimization problems, the MLP is NP-hard even on trees (Sitters, 2001). Our main result is an improved approximation algorithm for the MLP on trees, upon which we build improved approximation algorithms for a much wider class of graphs. The MLP on trees is interesting for several reasons. First, many of the aspects that make the problem difficult on general graphs are already present in the tree case. Second, all existing approximation algorithms for general graphs are built on approximation algorithms for the tree case. Third, there has been no improvement for the tree case since the 3.59-approximation of Goemans and Kleinberg, first introduced 14 years ago in 1996. Fourth, in the intervening period, the best ratio for general metrics has been improved to match the 3.59 for trees (Chaudhuri et al., 2003). In this paper, we improve the approximation ratio for trees to 3.03. In fact, our 3.03-approximation algorithm works for any class of graphs in which the related prize-collecting stroll (PCS) problem is solvable in polynomial time, such as graphs of constant treewidth. More generally, for any class of graphs that admit a Lagrangian-preserving β-approximation algorithm, we can use this algorithm as a black box to achieve a 3.03β-approximation for the MLP. Sadly, this does not immediately improve the ratio of 3.59 for general graphs, because the current best value of β for that case is 2. One interesting piece of our analysis is the solution of an infinite-dimensional linear program, used to analyze a finite-dimensional factor-revealing linear program (FRLP). We believe that our methods may hold promise for easing the analysis of other FRLPs encountered in the literature.
Starting Page	429
Ending Page	447
Page Count	19
File Format	PDF
ISBN	9780898716986
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-01-17
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