Improved approximation algorithms for label cover problems
From MaRDI portal
(Redirected from Publication:634686)
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
- 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
- scientific article; zbMATH DE number 1670859 (Why is no real title available?)
- scientific article; zbMATH DE number 5764908 (Why is no real title available?)
- 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
(25)- On the hardness of approximating label-cover
- On the approximability of the minimum rainbow subgraph problem and other related problems
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- Lasserre integrality gaps for graph spanners and related problems
- Minimum label \(s\)-\(t\) cut has large integrality gaps
- scientific article; zbMATH DE number 1617261 (Why is no real title available?)
- New results on the complexity of the Max- and Min-Rep problems
- A New Point of NP-Hardness for 2-to-1 Label Cover
- Improved Approximation Algorithms for Label Cover Problems
- Approximation algorithms for label cover and the log-density threshold
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Sherali-Adams integrality gaps matching the log-density threshold
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Improved approximation algorithms for projection games
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- scientific article; zbMATH DE number 7650076 (Why is no real title available?)
- Sum-of-squares lower bounds for densest k-subgraph
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- On approximate reconfigurability of label cover
- Pliability and approximating Max-CSPs
- The strongish planted clique hypothesis and its consequences
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
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)
