Polylogarithmic inapproximability

DOI10.1145/780542.780628zbMath1192.68321OpenAlexW2295961103MaRDI QIDQ3581278

Publication date: 16 August 2010

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

Full work available at URL: https://doi.org/10.1145/780542.780628

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (57)

Bounded Degree Group Steiner Tree Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ On approximating degree-bounded network design problems ⋮ Unnamed Item ⋮ Lehman's Theorem and the Directed Steiner Tree Problem ⋮ Approximation algorithms for the directed $k$-Tour and $k$-Stroll problems ⋮ Directed Steiner trees with diffusion costs ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ On the approximability of dense Steiner problems ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ Locating service and charging stations ⋮ Approximating node-connectivity augmentation problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized complexity of team formation in social networks ⋮ The relation of connected set cover and group Steiner tree ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Complexity and approximation of the connected set-cover problem ⋮ Adaptive Submodular Ranking and Routing ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ On the hardness of full Steiner tree problems ⋮ Approximating $k$-generalized connectivity via collapsing HSTs ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Complete partitions of graphs ⋮ How to Secure Matchings against Edge Failures ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ On approximating degree-bounded network design problems ⋮ On rooted $k$-connectivity problems in quasi-bipartite digraphs ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Balls and Funnels: Energy Efficient Group-to-Group Anycasts ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ How to Secure Matchings Against Edge Failures ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ The minimum degree group Steiner problem ⋮ Parameterized Complexity of Team Formation in Social Networks ⋮ The polymatroid Steiner problems ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Unnamed Item ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ Steiner Problems with Limited Number of Branching Nodes ⋮ On full Steiner trees in unit disk graphs ⋮ Approximability of capacitated network design ⋮ On rooted $k$-connectivity problems in quasi-bipartite digraphs ⋮ On fixed cost $k$-flow problems ⋮ Tight bounds on subexponential time approximation of set cover and related problems ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications

This page was built for publication: Polylogarithmic inapproximability