Weighted NP Optimization Problems: Logical Definability and Approximation Properties
- 1 January 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (1) , 36-56
- https://doi.org/10.1137/s0097539795285102
Abstract
No abstract availableThis publication has 11 references indexed in Scilit:
- Approximation Properties of NP Minimization ClassesJournal of Computer and System Sciences, 1995
- Logical Definability of NP Optimization ProblemsInformation and Computation, 1994
- Quantifiers and approximationTheoretical Computer Science, 1993
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1992
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- The Spectra of First-Order Sentences and Computational ComplexitySIAM Journal on Computing, 1984
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979