On weighted vs unweighted versions of combinatorial optimization problems
From MaRDI portal
Publication:1854428
DOI10.1006/inco.2000.3011zbMath1009.90094OpenAlexW2036930319MaRDI QIDQ1854428
Riccardo Silvestri, Luca Trevisan, Pierluigi Crescenzi
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/ab600f230474c1fe2a38d14ea95c5eb161985b2c
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On regularity of Max-CSPs and Min-CSPs ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ On percolation and ‐hardness ⋮ Quell ⋮ Unnamed Item ⋮ On Khot’s unique games conjecture ⋮ Introduction to the Maximum Solution Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramanujan graphs
- Optimization, approximation, and complexity classes
- Approximating maximum independent sets by excluding subgraphs
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- On approximation algorithms for the minimum satisfiability problem
- Two prover protocols
- Improved non-approximability results
- Vertex packings: Structural properties and algorithms
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- `` Strong NP-Completeness Results
- On the Approximation of Maximum Satisfiability
- Interactive proofs and the hardness of approximating cliques
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Efficient probabilistically checkable proofs and applications to approximations
