The hardness of approximation: Gap location
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3487716 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1256685 (Why is no real title available?)
- Explicit constructions of linear-sized superconcentrators
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- NP completeness of finding the chromatic index of regular graphs
- On the hardness of approximating minimization problems
- Optimization, approximation, and complexity classes
- P-Complete Approximation Problems
- Some simplified NP-complete graph problems
- The Complexity of Near-Optimal Graph Coloring
- The NP-Completeness of Edge-Coloring
- The Steiner problem with edge lengths 1 and 2
- The Traveling Salesman Problem with Distances One and Two
Cited in
(52)- Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
- The generalized assignment problem with minimum quantities
- Lossy kernelization of same-size clustering
- Shape rectangularization problems in intensity-modulated radiation therapy
- A parameterized approximation scheme for generalized partial vertex cover
- Inapproximability results for combinatorial auctions with submodular utility functions
- Computing densest \(k\)-subgraph with structural parameters
- Maximum bipartite flow in networks with adaptive channel width
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
- Approximation of satisfactory bisection problems
- Hardness of approximation for orthogonal rectangle packing and covering problems
- Minimizing total completion time with machine-dependent priority lists
- Maximum betweenness centrality: approximability and tractable cases
- On approximation of max-vertex-cover
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- Between a rock and a hard place: the two-to-one assignment problem
- Multi-dimensional vector assignment problems
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- An improved algorithm for parallel machine scheduling under additional resource constraints
- Partitioning a weighted partial order
- Improved approximations for max set splitting and max NAE SAT
- Approximating vector scheduling: almost matching upper and lower bounds
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Complexity of most vital nodes for independent set in graphs related to tree structures
- Proportional volume sampling and approximation algorithms for \(A\)-optimal design
- Approximation and hardness results for the maximum edges in transitive closure problem
- Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- The most vital nodes with respect to independent set and vertex cover
- Energy-efficient algorithms for non-preemptive speed-scaling
- Improved approximations for hard optimization problems via problem instance classification
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Spooky Encryption and Its Applications
- Inapproximability results for no-wait job shop scheduling.
- Scheduling with conflicts: Online and offline algorithms
- Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
- Hardness results for neural network approximation problems
- Zero knowledge and the chromatic number
- Exact algorithms for the matrix bid auction
- Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- Hard constraint satisfaction problems have hard gaps at location 1
- The minimum-entropy set cover problem
- Capacitated covering problems in geometric spaces
- The path partition problem and related problems in bipartite graphs
- Structure of polynomial-time approximation
- Maximizing coverage while ensuring fairness: a tale of conflicting objectives
- Hardness of \(k\)-vertex-connected subgraph augmentation problem
- On the cycle augmentation problem: hardness and approximation algorithms
- Balanced partitions of trees and applications
- Lossy kernelization of same-size clustering
This page was built for publication: The hardness of approximation: Gap location
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332662)
