The Library
From graph to hypergraph multiway partition : is the single threshold the only route?
Tools
Ene, Alina and Nguyễn, Huy L. (2014) From graph to hypergraph multiway partition : is the single threshold the only route? In: Schulz, Andreas S. and Wagner, Dorothea, 1957, (eds.) Algorithms  ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 810, 2014 : proceedings. Lecture notes in computer science (Number 8737). Berlin: Springer, pp. 382393. ISBN 9783662447765

PDF
WRAP_Ene_1273721cs121214hypermp.pdf  Accepted Version  Requires a PDF viewer. Download (652Kb)  Preview 
Official URL: http://dx.doi.org/10.1007/9783662447772_32
Abstract
We consider the Hypergraph Multiway Partition problem (HyperMP). The input consists of an edgeweighted hypergraph G=(V,ϵ) and k vertices s 1, …, s k called terminals. A multiway partition of the hypergraph is a partition (or labeling) of the vertices of G into k sets A 1, …, A k such that s i ∈ A i for each i ∈ [k]. The cost of a multiway partition (A 1, …, A k ) is ∑ki=1w(δ(Ai)), where w(δ(⋅)) is the hypergraph cut function. The HyperMP problem asks for a multiway partition of minimum cost.
Our main result is a 4/3 approximation for the HyperMP problem on 3uniform hypergraphs, which is the first improvement over the (1.5 − 1/k) approximation of [5]. The algorithm combines the singlethreshold rounding strategy of Calinescu et al. [3] with the rounding strategy of Kleinberg and Tardos [8], and it parallels the recent algorithm of Buchbinder et al.[2] for the Graph Multiway Cut problem, which is a special case.
On the negative side, we show that the KT rounding scheme [8] and the exponential clocks rounding scheme [2] cannot break the (1.5 − 1/k) barrier for arbitrary hypergraphs. We give a family of instances for which both rounding schemes have an approximation ratio bounded from below by Ω(k√), and thus the Graph Multiway Cut rounding schemes may not be sufficient for the HyperMP problem when the maximum hyperedge size is large. We remark that these instances have k = Θ(logn).
Item Type:  Book Item  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Hypergraphs, Partitions (Mathematics)  
Series Name:  Lecture notes in computer science  
Publisher:  Springer  
Place of Publication:  Berlin  
ISBN:  9783662447765  
ISSN:  03029743  
Book Title:  Algorithms  ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 810, 2014 : proceedings  
Editor:  Schulz, Andreas S. and Wagner, Dorothea, 1957  
Official Date:  2014  
Dates: 


Date of first compliant deposit:  27 March 2016  
Number:  Number 8737  
Page Range:  pp. 382393  
DOI:  10.1007/9783662447772_32  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Description: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year