On syntactic versus computational views of approximability
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- Approximation properties of NP minimization classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Improved approximations of independent sets in bounded-degree graphsPublished by Springer Nature ,1994
- New local search approximation techniques for maximum generalized satisfiability problemsPublished by Springer Nature ,1994
- .879-approximation algorithms for MAX CUT and MAX 2SATPublished by Association for Computing Machinery (ACM) ,1994
- Efficient probabilistically checkable proofs and applications to approximationsPublished by Association for Computing Machinery (ACM) ,1993
- On the hardness of approximating minimization problemsPublished by Association for Computing Machinery (ACM) ,1993
- On approximating the longest path in a graphPublished by Springer Nature ,1993
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Efficient bounds for the stable set, vertex cover and set packing problemsDiscrete Applied Mathematics, 1983