Universal approximations for TSP, Steiner tree, and set cover

DOI10.1145/1060590.1060649zbMath1192.68365OpenAlexW2130186928MaRDI QIDQ3581400

Rajaraman Rajmohan, Guevara Noubir, Lu Jun Jia, Guolong Lin, Ravi Sundaram

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.9158

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) General topics in the theory of algorithms (68W01)

Related Items

Packing a Knapsack of Unknown Capacity ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Load balanced distributed directories ⋮ Universal Guard Problems ⋮ Metric Embedding via Shortest Path Decompositions ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ Assouad-Nagata dimension and gap for ordered metric spaces ⋮ Universal Algorithms for Clustering Problems ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ Unnamed Item ⋮ Algorithms for the universal and a priori TSP ⋮ Optimal nearest neighbor queries in sensor networks ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Oblivious Buy-at-Bulk in Planar Graphs ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Time-communication impossibility results for distributed transactional memory ⋮ Unnamed Item