Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
- 1 February 1999
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 58 (1), 193-210
- https://doi.org/10.1006/jcss.1998.1605
Abstract
No abstract availableThis publication has 26 references indexed in Scilit:
- Randomness-efficient oblivious samplingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUTPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Probabilistic checking of proofsJournal of the ACM, 1998
- MAX-CUT has a randomized approximation scheme in dense graphsRandom Structures & Algorithms, 1996
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- Randomness in interactive proofscomputational complexity, 1993
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- The complexity of colouring problems on dense graphsTheoretical Computer Science, 1986
- Bin packing can be solved within 1 + ε in linear timeCombinatorica, 1981