On weighted vs unweighted versions of combinatorial optimization problems

DOI10.1006/INCO.2000.3011MaRDI QIDQ1854428zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Riccardo Silvestri, Luca Trevisan

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A note on the approximation of a minimum-weight maximal independent set
• Weighted NP Optimization Problems: Logical Definability and Approximation Properties
• Upper and lower bounds on approximating weighted mixed domination
• Improved approximations for weighted and unweighted graph problems
• Gadgets, Approximation, and Linear Programming

Cites work

• scientific article; zbMATH DE number 3708485 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256714 (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 1332666 (Why is no real title available?)
• scientific article; zbMATH DE number 2077131 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• Approximating maximum independent sets by excluding subgraphs
• Efficient probabilistically checkable proofs and applications to approximations
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Improved non-approximability results
• Interactive proofs and the hardness of approximating cliques
• On approximation algorithms for the minimum satisfiability problem
• On the Approximation of Maximum Satisfiability
• Optimization, approximation, and complexity classes
• Ramanujan graphs
• Two prover protocols, low error at affordable rates
• Vertex packings: Structural properties and algorithms
• `` Strong NP-Completeness Results

Cited in

(13)

• On Khot’s unique games conjecture
• Losing weight by gaining edges
• On percolation and \(\mathcal{NP}\)-hardness
• Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
• On regularity of Max-CSPs and Min-CSPs
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Possibilistic bottleneck combinatorial optimization problems with ill-known weights
• Introduction to the Maximum Solution Problem
• On approximability of linear ordering and related NP-optimization problems on graphs.
• The image of weighted combinatorial problems
• Quell
• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
• Fitting metrics and ultrametrics with minimum disagreements

This page was built for publication: On weighted vs unweighted versions of combinatorial optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854428)