Vertex cover might be hard to approximate to within 2 -
From MaRDI portal
Publication:2475406
Recommendations
Cites work
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- A Parallel Repetition Theorem
- An approximate zero-one law
- Approximating unique games
- Automata, Languages and Programming
- Boolean functions with low average sensitivity depend on few coordinates
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Conditional hardness for approximate coloring
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Hardness of Approximate Hypergraph Coloring
- scientific article; zbMATH DE number 3503316 (Why is no real title available?)
- scientific article; zbMATH DE number 2086690 (Why is no real title available?)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Near-optimal algorithms for unique games
- Non-approximability results for optimization problems on bounded degree instances
- On the hardness of approximating minimum vertex cover
- On the hardness of approximating Multicut and Sparsest-Cut
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Some optimal inapproximability results
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
Cited in
(only showing first 100 items - show all)- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Priority algorithms for graph optimization problems
- Dynamic algorithms via the primal-dual method
- Approximation for vertex cover in -conflict graphs
- Parameterized approximation via fidelity preserving transformations
- The stable roommates problem with short lists
- O(f) bi-criteria approximation for capacitated covering with hard capacities
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Network pollution games
- Maximally stable Gaussian partitions with discrete applications
- A kernel of order 2k-c k for vertex cover
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- Lift \& project systems performing on the partial-vertex-cover polytope
- Improved approximation algorithms for path vertex covers in regular graphs
- Approximation algorithm for the partial set multi-cover problem
- Approximation algorithm for the multicovering problem
- On the minimum vertex cover of generalized Petersen graphs
- Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds
- Approximation in (poly-) logarithmic space
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- Approximation algorithm for vertex cover with multiple covering constraints
- A simple rounding scheme for multistage optimization
- Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- Precedence-constrained covering problems with multiplicity constraints
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- Approximation algorithms for hitting subgraphs
- On the complexity of minimum \(q\)-domination partization problems
- Metric violation distance: hardness and approximation
- On dominating set of some subclasses of string graphs
- A reduction tree approach for the discrete time/cost trade-off problem
- Covering problem on fuzzy graphs and its application in disaster management system
- A primal-dual approximation algorithm for \textsc{minsat}
- Online learning for min-max discrete problems
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Improved approximation bounds for the minimum constraint removal problem
- Approximation of set multi-cover via hypergraph matching
- Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
- Iterative partial rounding for vertex cover with hard capacities
- Parallel approximation for partial set cover
- Metrical service systems with multiple servers
- Fixed-parameter tractability results for feedback set problems in tournaments
- New tools and connections for exponential-time approximation
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Integrality gap of the vertex cover linear programming relaxation
- A simple algorithm for the multiway cut problem
- A primal-dual algorithm for the minimum partial set multi-cover problem
- Partitioning a graph into small pieces with applications to path transversal
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- Obtaining matrices with the consecutive ones property by row deletions
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- The k-separator problem: polyhedra, complexity and approximation results
- Primal-dual algorithms for precedence constrained covering problems
- Tight approximation for partial vertex cover with hard capacities
- Vertex cover in conflict graphs
- On the generalized multiway cut in trees problem
- Flip distance between triangulations of a planar point set is APX-hard
- Undercover: a primal MINLP heuristic exploring a largest sub-MIP
- Randomized approximation for the set multicover problem in hypergraphs
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Pricing loss leaders can be hard
- The network-untangling problem: from interactions to activity timelines
- Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- Strong hardness of approximation for tree transversals
- Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
- On the d-claw vertex deletion problem
- Vertex cover meets scheduling
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- On the complexity landscape of the domination chain
- Bounds on 2-query locally testable codes with affine tests
- Optimal bounds on approximation of submodular and XOS functions by juntas
- The Stable Roommates Problem with Short Lists
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Approximating subdense instances of covering problems
- Exact and approximate algorithms for movement problems on (special classes of) graphs
- Moderately exponential time and fixed parameter approximation algorithms
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- The approximability of partial vertex covers in trees
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Approximating edge dominating set in dense graphs
- Vertex cover in graphs with locally few colors
- The uniform minimum-ones 2SAT problem and its application to haplotype classification
- Minimum vertex cover in generalized random graphs with power law degree distribution
- Approximation algorithms for minimum chain vertex deletion
- Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Approximability of economic equilibrium for housing markets with duplicate houses
- The label cut problem with respect to path length and label frequency
- Complexity of approximating CSP with balance/hard constraints
- Sequence hypergraphs
- Odd multiway cut in directed acyclic graphs
- Exact and approximate algorithms for movement problems on (special classes of) graphs
- Stabilizing weighted graphs
- Stable marriage and roommates problems with restricted edges: complexity and approximability
This page was built for publication: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2475406)
