skip to main content
10.1145/1007912.1007931acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
Article

Balanced graph partitioning

Published:27 June 2004Publication History

ABSTRACT

In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υn<over>k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2.

References

  1. Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In 27th Annual ACM Symposium on the Theory of Computing, pages 284--293, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Even, Naor, Rao, and Schieber. Fast approximate graph partitioning algorithms. SIAM Journal of Computing, 28(6):2187--2214, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approximation algorithms using spreading metrics. Journal of the ACM(JACM), 47(4):585--616, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. U. Feige, R. Krauthgamer, and K. Nissim. Approximating the minimum bisection size. In 32nd Annual ACM Symposium on the Theory of Computing, pages 530--536, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM Journal on Computing, 31(4):1090--1118, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In 19th IEEE Design Automation Conference, pages 175--181, 1982. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co, San Francisco, CA, 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. D. Hochbaum and D. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3):539--551, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. B.W. Kernighan and S. Lin. An efficient heuristic for partitioning graphs. Bell Sys. Tech. Journal, 49:291--308, 1970.Google ScholarGoogle Scholar
  10. T. Leighton, F. Makedon, and S. Tragoudas. Approximation algorithms for vlsi partition problems. In IEEE International Symposium on Circuits and Systems, (ISCAS '90), volume 4, pages 2865--2868, 1990.Google ScholarGoogle ScholarCross RefCross Ref
  11. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM(JACM), 46(6):787--832, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Huzur Saran and Vijay V. Vazirani. Finding k-cuts within twice the optimal. SIAM Journal of Computing, 24(1):101--108, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? SIAM Journal on Scientific Computing, 18(5):1436--1445, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Balanced graph partitioning

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures
        June 2004
        332 pages
        ISBN:1581138407
        DOI:10.1145/1007912

        Copyright © 2004 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 27 June 2004

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

        Overall Acceptance Rate447of1,461submissions,31%

        Upcoming Conference

        SPAA '24

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader