NDLI: Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Content Provider	Springer Nature Link
Author	Xiao, Mingyu Cai, Leizhen Yao, Andrew Chi Chih
Copyright Year	2009
Abstract	For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter.A simple algorithm for approximating a minimum k-way cut is to iteratively increase the number of components of the graph by h−1, where 2≤h≤k, until the graph has k components. The approximation ratio of this algorithm is known for h≤3 but is open for h≥4.In this paper, we consider a general algorithm that successively increases the number of components of the graph by h i−1, where 2≤h 1≤h 2≤⋅⋅⋅≤h q and ∑i=1q(h i−1)=k−1. We prove that the approximation ratio of this general algorithm is $2-(\sum_{i=1}^{q}{h_{i}\choose2})/{k\choose2}$ , which is tight. Our result implies that the approximation ratio of the simple iterative algorithm is 2−h/k+O(h 2/k 2) in general and 2−h/k if k−1 is a multiple of h−1.
Starting Page	510
Ending Page	520
Page Count	11
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	59
Issue Number	4
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-05-08
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	k-way cut Approximation algorithm Data Structures, Cryptology and Information Theory Computer Systems Organization and Communication Networks Algorithms Mathematics of Computing Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

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

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem

Tight Results on Minimum Entropy Set Cover

Approximation Algorithms for k-hurdle Problems

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

Approximation Algorithms for Requirement Cut on Graphs

Greedy Matching: Guarantees and Limitations

An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Similar Documents

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem

Tight Results on Minimum Entropy Set Cover

Approximation Algorithms for k-hurdle Problems

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

Approximation Algorithms for Requirement Cut on Graphs

Greedy Matching: Guarantees and Limitations

An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem