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 8-10, 2014 : proceedings. Lecture notes in computer science (Number 8737). Berlin: Springer, pp. 382-393. ISBN 9783662447765
|
PDF
WRAP_Ene_1273721-cs-121214-hyper-mp.pdf - Accepted Version - Requires a PDF viewer. Download (652Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-44777-2_32
Abstract
We consider the Hypergraph Multiway Partition problem (Hyper-MP). The input consists of an edge-weighted 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 Hyper-MP problem asks for a multiway partition of minimum cost.
Our main result is a 4/3 approximation for the Hyper-MP problem on 3-uniform hypergraphs, which is the first improvement over the (1.5 − 1/k) approximation of [5]. The algorithm combines the single-threshold 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 Hyper-MP 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, Engineering and Medicine > 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: | 0302-9743 | ||||
Book Title: | Algorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014 : proceedings | ||||
Editor: | Schulz, Andreas S. and Wagner, Dorothea, 1957- | ||||
Official Date: | 2014 | ||||
Dates: |
|
||||
Number: | Number 8737 | ||||
Page Range: | pp. 382-393 | ||||
DOI: | 10.1007/978-3-662-44777-2_32 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | |||||
Date of first compliant deposit: | 27 March 2016 | ||||
Date of first compliant Open Access: | 27 March 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year