Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs

DOI10.1007/978-3-642-22935-0_7zbMath1343.68307arXiv1011.3770OpenAlexW2110655989MaRDI QIDQ3088084

Sanjeev Khanna, Deeparnab Chakrabarty, Anand Bhalgat

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.3770

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

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 ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Unnamed Item

Uses Software

• PrivateLR

Cites Work

• Ramanujan graphs
• The geometry of graphs and some of its algorithmic applications
• Extensions and limits to vertex sparsification
• Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
• Expander graphs and their applications
• Universal approximations for TSP, Steiner tree, and set cover
• Improved lower and upper bounds for universal TSP in planar metrics
• Oblivious network design
• Improved Lower Bounds for the Universal and a priori TSP
• Dynamic Steiner Tree Problem
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• A tight bound on approximating arbitrary metrics by tree metrics
• Differential Privacy
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs