NDLI: Multi-way partitioning using bi-partition heuristics

Content Provider	IEEE Xplore Digital Library
Author	Maogang Wang Sung Kyu Lim Cong, J. Sarrafzadeh, M.
Copyright Year	2000
Description	Author affiliation: ECE Dept., Northwestern Univ., Evanston, IL, USA (Maogang Wang)
Abstract	The multi-way partition problem is very important in various applications. In this paper, we use analytical and experimental results to study the k-way partition problem. We introduce the concept of embedding graph for the the k-way partition problem. Based on this concept, we explain different scenarios of using a bi-partition heuristic to solve the k-way partition problem. If C denote the optimal cut cost for the k-way partition problem and the bi-partition heuristics we use are /spl delta/-approximation heuristics, we prove that the cut cost from the hierarchical approach has an approximate upper bound of /spl delta/C/spl middot/log k while the cut cost from the all-way bi-partition, or flat approach, has an upper bound of /spl delta/Ck. This is contrary to some claims made in the recent literature (and CAD tools designed based on it). Experimental results strongly support our theoretical analysis. Our results show that for large target graph, the hierarchical approach is about 77% better than the single-pass all-way bi-partition approach. The all-way bi-partition approach will perform better in a multipass set-up. However, the hierarchical approach is still on average 7.1% better in quality and 144 times faster than the multi-partition all-way bi-partition approach. The main conclusion of this paper is that, contradictary to what has been suggested in literature, hierarchical bi-partitioning is a more effective multi-way partitioning scheme.
Starting Page	667
Ending Page	672
File Size	652701
Page Count	6
File Format	PDF
ISBN	0780359739
DOI	10.1109/ASPDAC.2000.835183
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-01-25
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Cost function Partitioning algorithms Upper bound Design automation Very large scale integration Joining processes Tiles
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bipartitioning circuits using TABU search

Multi-way Partitioning Using Bi-partition Heuristics (2000)

Congestion-driven placement using a new multi-partitioning heuristic

On multilevel circuit partitioning

Multiway partitioning using bi-partition heuristics (2000)

Multi-way partitioning using bi-partition heuristics

New algorithms for min-cut replication in partitioned circuits

Finding balanced graph bi-partitions using a hybrid genetic algorithm

Efficient Network Flow Based Min-cut Balanced Partitioning

Multi-way partitioning using bi-partition heuristics

Similar Documents

Bipartitioning circuits using TABU search

Multi-way Partitioning Using Bi-partition Heuristics (2000)

Congestion-driven placement using a new multi-partitioning heuristic

On multilevel circuit partitioning

Multiway partitioning using bi-partition heuristics (2000)

Multi-way partitioning using bi-partition heuristics

New algorithms for min-cut replication in partitioned circuits

Finding balanced graph bi-partitions using a hybrid genetic algorithm

Efficient Network Flow Based Min-cut Balanced Partitioning

Multi-way partitioning using bi-partition heuristics