Skip to main content
SpringerLink
Log in

On Some Tighter Inapproximability Results (Extended Abstract)

  • Conference paper
  • First Online:
Automata, Languages and Programming

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1644))

Abstract

We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. N. Alon, U. Feige, A. Wigderson and D. Zuckerman, Derandomized Graph Products, Computational Complexity 5 (1995), pp. 60–75.

    Article  MathSciNet  Google Scholar 

  2. S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems, Ph. D. Thesis, UC Berkeley, 1994; available as TR94-476 at ftp://ftp.cs.princeton.edu

    Google Scholar 

  3. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Hardness of Approximation Problems, Proc. 33rd IEEE FOCS (1992), pp. 14–23.

    Google Scholar 

  4. V. Bafna and P. Pevzner, Genome rearrangements and sorting by reversals, SIAM J. on Computing 25 (1996), pp. 272–289.

    Article  MathSciNet  Google Scholar 

  5. P. Berman and T. Fujito, Approximating Independent Sets in Degree 3 Graphs, Proc. 4thWorkshop on Algorithms and Data Structures, LNCS Vol. 955, Springer-Verlag, 1995, pp. 449–460.

    Chapter  Google Scholar 

  6. P. Berman and M. Fürer, Approximating Maximum Independent Set in Bounded Degree Graphs, Proc. 5th ACM-SIAM SODA (1994), pp. 365–371.

    Google Scholar 

  7. P. Berman and S. Hannenhali, Fast Sorting by Reversals, Proc. 7th Symp. on Combinatorial Pattern Matching, 1996, pp. 168–185.

    Google Scholar 

  8. P. Berman and M. Karpinski, On Some Tighter Inapproximbility Results, preliminary version appeared in ECCC TR98-065, the full version available under http://theory.cs.uni-bonn.de/_marek.

  9. P. Berman and G. Schnitger, On the Complexity of Approximating the Independent Set Problem, Information and Computation 96 (1992), pp. 77–94.

    Article  MathSciNet  Google Scholar 

  10. B. Bollobás, Extremal Graph Theory, 1978, Academic Press.

    Google Scholar 

  11. A. Caprara, Sorting by reversals is difficult, Proc. 1st ACM RECOMB (Int. Conf. on Computational Molecular Biology), 1997, pp. 75–83.

    Google Scholar 

  12. D.A. Christie, A 3/2-Approximation Algorithm for Sorting by Reversals, Proc. 9th ACM-SIAM SODA (1998), pp. 244–252.

    Google Scholar 

  13. D. Cohen and M. Blum, Improved Bounds for Sorting Burnt Pancakes, Discrete Applied Mathematics, Vol. 61, pp. 105–125.

    Google Scholar 

  14. P. Crescenzi and V. Kann, A Compendium of NP Optimization Problems, Manuscript, 1997; available at http://www.nada.kth.se/theory/problemlist.html

  15. U. Feige and M. Goemans, Approximating the Value of Two Prover Proof Systems with Applications to MAX-2SAT and MAX-DICUT, Proc. 3rd Israel Symp. on Theory of Computing and Systems, 1995, pp. 182–189.

    Google Scholar 

  16. W.H. Gates, and C.H. Papadimitriou, Bounds for Sorting by Prefix Reversals, Discrete Mathematics 27 (1979), pp. 47–57.

    Article  MathSciNet  Google Scholar 

  17. M. Goemans and D. Williamson, 878-Approximation Algorithms for MAX CUT and MAX 2SAT, Proc. 26th ACM STOC (1994), pp. 422–431.

    Google Scholar 

  18. J. Håstad, Clique is Hard to Approximate within n1-ε, Proc. 37th IEEE FOCS (1996), pp. 627–636.

    Google Scholar 

  19. J. Håstad, Some optimal Inapproximability results, Proc. 29th ACMSTOC, 1997, pp. 1–10.

    Google Scholar 

  20. S. Hannenhali and P. Pevzner, Transforming Cabbage into Turnip (Polynomial time algorithm for sorting by reversals), Proc. 27th ACM STOC (1995), pp. 178–187.

    Google Scholar 

  21. H. Kaplan, R. Shamir and R.E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proc. 8th ACM-SIAM SODA, 1997, pp. 344–351.

    Google Scholar 

  22. C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, JCSS 43, 1991, pp. 425–440.

    MathSciNet  MATH  Google Scholar 

  23. L. Trevisan, G. Sorkin, M. Sudan and D. Williamson, Gadgets, Approximation and Linear Programming, Proc. 37th IEEE FOCS (1996), pp. 617–626.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Pennsylvania State University, University Park, PA, 16802, USA

    Piotr Berman

  2. Dept. of Computer Science, University of Bonn, 53117, Bonn, USA

    Marek Karpinski

Authors
  1. Piotr Berman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marek Karpinski
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute for Computer Science, Academy of Sciences of the Czech Republic, Pod vodarenskou vezi 2, 182 07, Prague 8 - Liben, Czech Republic

    Jirí Wiedermann

  2. ILLC-WINS-University of Amsterdam, Plantage Muidergracht 24, 1018, TV, Amsterdam, The Netherlands

    Peter van Emde Boas

  3. BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, Bldg. 540, DK, 8000, Aarhus C, Denmark

    Mogens Nielsen

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Berman, P., Karpinski, M. (1999). On Some Tighter Inapproximability Results (Extended Abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds) Automata, Languages and Programming. Lecture Notes in Computer Science, vol 1644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48523-6_17

Download citation

  • DOI: https://doi.org/10.1007/3-540-48523-6_17

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-66224-2

  • Online ISBN: 978-3-540-48523-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation