The Densest k-Subhypergraph Problem-猫眼课题宝

DOI：

10.4230/lipics.approx-random.2016.6

发表时间：

2016-05

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

E. Chlamtác;M. Dinitz;C. Konrad;G. Kortsarz;George Rabanca

最密集的K-Subgraph（DKS）问题及其相应的最小化问题最小的P边缘子图（SPE）已经在近似算法中起着核心作用。为了解决和建立其他问题的近似范围。（尽管最著名的硬度结果并不排除本文）。 k的k顶点的v v，以最大程度地提高W）中包含的高音数量并定义最小p-工会问题（给定超图，请选择“超蛋白的P”，以最大程度地减少其联合中的顶点的数量）。我们尤其关注所有Hyperedges具有3尺寸的情况，因为这是最简单的非图形设置。（任意常数> 0）对于最小p-工会，我们的最小值（√m）approximation在一般中，我们在一般的超graphs中为最小的p-工会提供了最小的p-工会一个有趣的间隔案例HyperGraphs（顶点是自然数的子集和HyperEdges的一个间隔），并且证明这两个问题都在本Gurion University的计算机科学系中允许精确的多项式时间解决方案ISF赠款1002/14。 1535887。美国纽约州卡姆登大学，由NSF赠款1218620和1540547。计算机科学，美国CUNY，电子邮件：grabanca@gmail.com ar x IV：1 60 5.04 28 4V 1 [CS .D S] 1 3 M AY 2 01 6

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 ⊆ 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(n4(4− √ 3)/13+ ) ≤ O(n )-approximation (for arbitrary constant > 0) for Densest k-Subhypergraph and an O(n)-approximation for Minimum p-Union. We also give an O( √ 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. ∗Department of Computer Science, Ben Gurion University. Partially supported by ISF grant 1002/14. Email: chlamtac@cs.bgu.ac.il. †Department of Computer Science, Johns Hopkins University. Partially supported by NSF grants 1464239 and 1535887. Email: mdinitz@cs.jhu.edu ‡ICE-TCS, School of Computer Science, Reykjavik University. Supported by Icelandic Research Fund grants 120032011 and 152679-051. Email: christiank@ru.is. §Computer Science Department, Rutgers University, Camden, NY, USA. Partially supported by NSF grants 1218620 and 1540547. Email: guyk@crab.rutgers.edu ¶Department of Computer Science, The Graduate Center, CUNY, USA. Email: grabanca@gmail.com ar X iv :1 60 5. 04 28 4v 1 [ cs .D S] 1 3 M ay 2 01 6

The Densest k-Subhypergraph Problem

文献摘要

被引文献

相似文献