1 Search Results for "Foschini, Luca"

Document

DOI: 10.4230/LIPIcs.STACS.2012.100

Balanced Partitions of Trees and Applications

Authors: Andreas Emil Feldmann and Luca Foschini

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract

We study the k-BALANCED PARTITIONING problem in which the vertices of a graph are to be partitioned into k sets of size at most ceil(n/k) while minimising the cut size, which is the number of edges connecting vertices in different sets. The problem is well studied for general graphs, for which it cannot be approximated within any factor in polynomial time. However, little is known about restricted graph classes. We show that for trees k-BALANCED PARTITIONING remains surprisingly hard. In particular, approximating the cut size is APX-hard even if the maximum degree of the tree is constant. If instead the diameter of the tree is bounded by a constant, we show that it is NP-hard to approximate the cut size within n^c, for any constant c<1. In the face of the hardness results, we show that allowing near-balanced solutions, in which there are at most (1+eps)ceil(n/k) vertices in any of the k sets, admits a PTAS for trees. Remarkably, the computed cut size is no larger than that of an optimal balanced solution. In the final section of our paper, we harness results on embedding graph metrics into tree metrics to extend our PTAS for trees to general graphs. In addition to being conceptually simpler and easier to analyse, our scheme improves the best factor known on the cut size of near-balanced solutions from O(log^{1.5}(n)/eps^2) [Andreev and Räcke TCS 2006] to 0(log n), for weighted graphs. This also settles a question posed by Andreev and Räcke of whether an algorithm with approximation guarantees on the cut size independent from eps exists.

Cite as

Andreas Emil Feldmann and Luca Foschini. Balanced Partitions of Trees and Applications. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 100-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.STACS.2012.100,
  author =	{Feldmann, Andreas Emil and Foschini, Luca},
  title =	{{Balanced Partitions of Trees and Applications}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{100--111},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.100},
  URN =		{urn:nbn:de:0030-drops-34081},
  doi =		{10.4230/LIPIcs.STACS.2012.100},
  annote =	{Keywords: balanced partitioning, bicriteria approximation, hardness of approximation, tree embeddings}
}

Refine by Author
1 Feldmann, Andreas Emil
1 Foschini, Luca

Refine by Classification

Refine by Keyword
1 balanced partitioning
1 bicriteria approximation
1 hardness of approximation
1 tree embeddings

Refine by Type
1 document

Refine by Publication Year
1 2012

1 Search Results for "Foschini, Luca"

Balanced Partitions of Trees and Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message