Improved approximation algorithms for label cover problems
From MaRDI portal
Recommendations
- Improved Approximation Algorithms for Label Cover Problems
- Approximation algorithms for label cover and the log-density threshold
- New results on the complexity of the Max- and Min-Rep problems
- On the hardness of approximating label-cover
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
Cites work
- scientific article; zbMATH DE number 1670859 (Why is no real title available?)
- scientific article; zbMATH DE number 5764908 (Why is no real title available?)
- Approximating the minimal sensor selection for supervisory control
- Approximation Algorithms and Hardness for Domination with Propagation
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- Design networks with bounded pairwise distance
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Disjoint-path facility location: theory and practice
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- On network design problems: fixed cost flows and the covering steiner problem
- On the hardness of approximating spanners
- Power optimization for connectivity problems
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Stochastic Steiner Tree with Non-uniform Inflation
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The hardness of approximating spanner problems
- Transitive-closure spanners
Cited in
(20)- Minimum label \(s\)-\(t\) cut has large integrality gaps
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- A New Point of NP-Hardness for 2-to-1 Label Cover
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- Improved Approximation Algorithms for Label Cover Problems
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Lasserre integrality gaps for graph spanners and related problems
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- On the approximability of the minimum rainbow subgraph problem and other related problems
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Approximation algorithms for label cover and the log-density threshold
- scientific article; zbMATH DE number 1617261 (Why is no real title available?)
- New results on the complexity of the Max- and Min-Rep problems
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- scientific article; zbMATH DE number 7650076 (Why is no real title available?)
- On the hardness of approximating label-cover
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Sherali-Adams integrality gaps matching the log-density threshold
- Improved approximation algorithms for projection games
This page was built for publication: Improved approximation algorithms for label cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634686)
