SpringerLink
Log in

Some Recent Progress for Approximation Algorithms

  • Chapter
Principles and Methods of Quantum Information Technologies

Part of the book series: Lecture Notes in Physics ((LNP,volume 911))

  • 5032 Accesses

Abstract

We survey some recent progress on approximation algorithms. Our main focus is the following two problems that have some recent breakthroughs; the edge-disjoint paths problem and the graph coloring problem. These breakthroughs involve the following three ingredients that are quite central in approximation algorithms: (1) Combinatorial (graph theoretical) approach, (2) LP based approach and (3) Semi-definite programming approach. We also sketch how they are used to obtain recent development.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, and by Mitsubishi Foundation.

References

  1. M. Andrews, J. Chuzhoy, S. Khanna, L. Zhang, Hardness of the undirected edge-disjoint paths problem with congestion, in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh (2005), pp. 226–244

    Google Scholar 

  2. S. Arora, E. Chlamtac, M. Charikar, New approximation guarantee for chromatic number, in Proceedings of the 38th STOC, Seattle (2006) pp. 215–224

    Google Scholar 

  3. S. Arora, S. Rao, U. Vazirani, Expanders, geometric embeddings and graph partitioning. J. ACM 56(2), 1–37 (2009). Announced at STOC’04

    Google Scholar 

  4. B. Berger, J. Rompel, A better performance guarantee for approximate graph coloring. Algorithmica, 5(3), 459–466 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  5. A. Blum, New approximation algorithms for graph coloring. J. ACM 41(3), 470–516 (1994). Announced at STOC’89 and FOCS’90

    Google Scholar 

  6. A. Blum, D. Karger, An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett. 61(1), 49–53 (1997)

    Article  MathSciNet  Google Scholar 

  7. C. Chekuri, S. Khanna, B. Shepherd, The all-or-nothing multicommodity flow problem, in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago (2004), pp. 156–165

    Google Scholar 

  8. C. Chekuri, S. Khanna, B. Shepherd, An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2, 137–146 (2006)

    Article  MathSciNet  Google Scholar 

  9. C. Chekuri, S. Khanna, B. Shepherd, Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput. 39, 281–301 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  10. E. Chlamtac, Approximation algorithms using hierarchies of semidefinite programming relaxations, in Proceedings of the 48th FOCS, Providence (2007), pp. 691–701

    Google Scholar 

  11. J. Chuzhoy, S. Li, A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2, in Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS), New Brunswick (2012), pp. 233–242

    Google Scholar 

  12. I. Dinur, E. Mossel, O. Regev, Conditional hardness for approximate coloring. SIAM J. Comput. 39(3), 843–873 (2009). Announced at STOC’06

    Google Scholar 

  13. S. Even, A. Itai, A. Shamir, On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5, 691–703 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  14. U. Feige, J. Kilian, Zero-knowledge and the chromatic number. J. Comput. Syst. Sci. 57, 187–199 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  15. U. Feige, M. Langberg, G. Schechtman, Graphs with tiny vector chromatic numbers and huge chromatic numbers, In Proceedings of the 43rd FOCS, Vancouver (2002), pp. 283–292

    Google Scholar 

  16. A. Frank, Packing paths, cuts and circuits – a survey, in Paths, Flows and VLSI-Layout, ed. by B. Korte, L. Lovász, H.J. Promel, A. Schrijver (Springer, Berlin, 1990), pp. 49–100

    Google Scholar 

  17. M. Garey, D. Johnson, L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976). Announced at STOC’74

    Google Scholar 

  18. N. Garg, V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3–20 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. M. Goemansl, D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995). Announced at STOC’94

    Google Scholar 

  20. V. Guruswami, S. Khanna, On the hardness of 4-coloring a 3-colorable graph. J. Discret. Math. 18(1), 30–40 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, M. Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67, 473–496 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. J. Håstad, Clique is hard to approximate within \(n^{1-\varepsilon }\). Acta Math. 182, 105–142 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  23. D. Karger, R. Motwani, M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM 45(2), 246–265 (1998). Announced at FOCS’94

    Google Scholar 

  24. R.M. Karp, On the computational complexity of combinatorial problems. Networks 5, 45–68 (1975)

    MATH  MathSciNet  Google Scholar 

  25. K. Kawarabayashi, Y. Kobayashi, An improved algorithm for the half-disjoint paths problem. SIAM J. Discret. Math. 25, 1322–1330 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  26. K. Kawarabayashi, Y. Kobayashi, All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, in The 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), Berkeley (2013), pp.187–196

    Google Scholar 

  27. K. Kawarabayashi, B. Reed, A nearly linear time algorithm for the half integral disjoint paths packing, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco (2008), pp. 446–454

    Google Scholar 

  28. K. Kawarabayashi, M. Thorup, Combinatorial coloring of 3-colorable graphs, in Proceedings of the 53rd FOCS, New Brunswick (2012)

    Google Scholar 

  29. K. Kawarabayashi, M. Thorup, Coloring 3-colorable graphs with o(n 1∕5) colors, in The 31st Symposium on Theoretical Aspects of Computer Science (STACS’14), Lyon (2014), pp. 458–469

    Google Scholar 

  30. K. Kawarabayashi, Y. Kobayashi, B. Reed, The disjoint paths problem in quadratic time. J. Combin. Theory Ser. B 102, 424–435 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  31. S. Khanna, N. Linial, S. Safra, On the hardness of approximating the chromatic number. Combinatorica 20(3), 393–415 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  32. J. Kleinberg, Decision algorithms for unsplittable flow and the half-disjoint paths problem, in Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), Dallas (1998), pp. 530–539

    Google Scholar 

  33. M.R. Kramer, J. van Leeuwen, The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res. 2, 129–146 (1984)

    Google Scholar 

  34. N. Robertson, P.D. Seymour, Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63, 65–110 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  35. A. Schrijver, A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  36. A. Schrijver, in Combinatorial Optimization: Polyhedra and Efficiency. Algorithm and Combinatorics, vol. 24 (Springer, Berlin/New York, 2003)

    Google Scholar 

  37. L. Séguin-Charbonneau, B.F. Shepherd, Maximum edge-disjoint paths in planar graphs with congestion 2, in Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs (2011), pp. 200–209

    Google Scholar 

  38. M. Szegedy, A note on the \(\theta\) number of Lovász and the generalized Delsarte bound, in Proceedings of the 35th FOCS, Santa Fe (1994), pp. 36–39

    Google Scholar 

  39. A. Wigderson, Improving the performance guarantee for approximate graph coloring. J. ACM 30(4), 729–735 (1983). Announced at STOC’82

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Institute of Informatics, JST ERATO Kawarabayashi Project, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan

    Ken-ichi Kawarabayashi

Authors
  1. Ken-ichi Kawarabayashi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ken-ichi Kawarabayashi .

Editor information

Editors and Affiliations

  1. ImPACT Program, Council for Science Technology and Innovation, Tokyo, Japan

    Yoshihisa Yamamoto

  2. National Institute of Information and Communications Technology, Koganei, Tokyo, Japan

    Kouichi Semba

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Japan

About this chapter

Cite this chapter

Kawarabayashi, Ki. (2016). Some Recent Progress for Approximation Algorithms. In: Yamamoto, Y., Semba, K. (eds) Principles and Methods of Quantum Information Technologies. Lecture Notes in Physics, vol 911. Springer, Tokyo. https://doi.org/10.1007/978-4-431-55756-2_9

Download citation

Publish with us

Policies and ethics

Search

Navigation