1 Search Results for "Rabanca, George"


Document
The Densest k-Subhypergraph Problem

Authors: Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)


Abstract
The Densest k-Subgraph (DkS) problem, and its corresponding minimization problem Smallest p-Edge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest k-Subhypergraph problem (given a hypergraph (V, E), find a subset W subseteq V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an O(n^{4(4-sqrt{3})/13 + epsilon}) <= O(n^{0.697831+epsilon})-approximation (for arbitrary constant epsilon > 0) for Densest k-Subhypergraph and an ~O(n^{2/5})-approximation for Minimum p-Union. We also give an O(sqrt{m})-approximation for Minimum p-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.

Cite as

Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. The Densest k-Subhypergraph Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2016.6,
  author =	{Chlamtac, Eden and Dinitz, Michael and Konrad, Christian and Kortsarz, Guy and Rabanca, George},
  title =	{{The Densest k-Subhypergraph Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  URN =		{urn:nbn:de:0030-drops-66298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  annote =	{Keywords: Hypergraphs, Approximation algorithms}
}
  • Refine by Author
  • 1 Chlamtac, Eden
  • 1 Dinitz, Michael
  • 1 Konrad, Christian
  • 1 Kortsarz, Guy
  • 1 Rabanca, George

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 Hypergraphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail