Polylogarithmic inapproximability
From MaRDI portal
Recommendations
- Approximation in (poly-) logarithmic space
- Approximation in (Poly-) Logarithmic Space
- Inapproximability of the Tutte polynomial
- Inapproximability of the Tutte polynomial
- On polylogarithms
- scientific article; zbMATH DE number 510287
- Polylogarithms
- Inapproximability of the independent set polynomial in the complex plane
- Inapproximability of the independent set polynomial in the complex plane
- A Polylogarithmic Bound in the Nonlinear Roth Theorem
Cited in
(72)- Parameterized complexity of team formation in social networks
- The minimum degree group Steiner problem
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Tight bounds on subexponential time approximation of set cover and related problems
- On approximating degree-bounded network design problems
- A polylogarithmic approximation algorithm for 2-edge-connected dominating set
- On full Steiner trees in unit disk graphs
- Approximability of capacitated network design
- Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
- Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
- Approximating node-connectivity augmentation problems
- Bounded-hops power assignment in ad hoc wireless networks
- The polymatroid Steiner problems
- A greedy approximation algorithm for the group Steiner problem
- On fixed cost k-flow problems
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Balls and funnels: energy efficient group-to-group anycasts
- Parameterized complexity of team formation in social networks
- Steiner problems with limited number of branching nodes
- 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)
- An Efficient Approximation Algorithm for the Steiner Tree Problem
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Lehman's theorem and the directed Steiner tree problem
- Directed Steiner trees with diffusion costs
- A practical greedy approximation for the directed Steiner tree problem
- On the approximability of dense Steiner problems
- The relation of connected set cover and group Steiner tree
- Complexity and approximation of the connected set-cover problem
- Spider covering algorithms for network design problems
- On the hardness of full Steiner tree problems
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- Survivable network design for group connectivity in low-treewidth graphs
- Parameterized approximation algorithms for bidirected Steiner network problems
- Bounded Degree Group Steiner Tree Problems
- Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- How to Secure Matchings Against Edge Failures
- Adaptive submodular ranking and routing
- Cost-optimal planning, delete relaxation, approximability, and heuristics
- How to Secure Matchings against Edge Failures
- Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
- A PTAS for the Steiner forest problem in doubling metrics
- Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
- scientific article; zbMATH DE number 7053371 (Why is no real title available?)
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- scientific article; zbMATH DE number 7662164 (Why is no real title available?)
- $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
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Locating service and charging stations
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Better trees for Santa Claus
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- The parameterized complexity of the survivable network design problem
- Parameterized algorithms for the Steiner arborescence problem on a hypercube
- On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
- A logarithmic integrality gap for generalizations of quasi-bipartite instances of directed Steiner tree
- A \(O(\log k)\)-approximation for \textsc{Directed Steiner Tree} in planar graphs
- Degrees and network design: new problems and approximations
- Polynomial integrality gap of flow LP for directed Steiner tree
- Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
- Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime
- Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
- From directed Steiner tree to directed polymatroid Steiner tree in planar graphs
- Complexity and approximation algorithms for fixed charge transportation problems
- A PTAS for TSP with neighbourhoods over parallel line segments
- Complexity and approximation algorithms for fixed charge transportation problems
- Tight approximation algorithm for connectivity augmentation problems
- Complete partitions of graphs
This page was built for publication: Polylogarithmic inapproximability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581278)
