{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T15:13:38Z","timestamp":1790176418670,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1002\/14"],"award-info":[{"award-number":["1002\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218620"],"award-info":[{"award-number":["1218620"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1540547"],"award-info":[{"award-number":["1540547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1464239"],"award-info":[{"award-number":["1464239"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1535887"],"award-info":[{"award-number":["1535887"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N011163\/1"],"award-info":[{"award-number":["EP\/N011163\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The densest $k$-subgraph (D$k$S) problem and its corresponding minimization problem smallest $p$-edge subgraph (S$p$ES) have come to play a central role in approximation algorithms. This is due both to their practical importance and to 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 admit a subpolynomial approximation ratio (although the best-known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the densest $k$-subhypergraph (D$k$SH) 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 (M$p$U) 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 nongraph setting. For this case we provide an $O(n^{4(4-\\sqrt{3})\/13 + \\epsilon}) &lt; O(n^{0.697831+\\epsilon})$-approximation (for arbitrary constant $\\epsilon &gt; 0$) for D$k$SH and an $\\tilde{O}(n^{2\/5})$-approximation for M$p$U. We also give an $O(\\sqrt{m})$-approximation for M$p$U 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.<\/jats:p>","DOI":"10.1137\/16m1096402","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T11:39:57Z","timestamp":1530185997000},"page":"1458-1477","source":"Crossref","is-referenced-by-count":37,"title":["The Densest $k$-Subhypergraph Problem"],"prefix":"10.1137","volume":"32","author":[{"given":"Eden","family":"Chlamt\u00e1\u010d","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Dinitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Konrad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Rabanca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"atypb1","unstructured":"N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein,\n                      Inapproximability of Densest k-Subgraph from Average Case Hardness\n                      , manuscript, 2011."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120884857"},{"key":"atypb3","first-page":"171","author":"Applebaum B.","year":"2010","journal-title":"AXM"},{"key":"atypb4","unstructured":"S. Arora, B. Barak, M. Brunnermeier, and R. Ge,\n                      Complicational Complexity and Information Asymmetry in Finnancial Products\n                      , manuscript, 2016."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Arora and R. Ge,\n                      New tools for graph coloring\n                      , in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, APPROX 2011, RANDOM 2011, Lecture Notes in Comput. Sci. 6845, L. A. Goldberg, K. Jansen, R. Ravi, and J. D. P. Rolim, eds., Springer, Berlin, Heidelberg, 2011, pp. 1-12.","DOI":"10.1007\/978-3-642-22935-0_1"},{"key":"atypb6","unstructured":"A. Bhaskara,\n                      Finding Dense Structures in Graphs and Matrices\n                      , Ph.D. thesis, Princeton University, Princeton, NJ, 2012."},{"key":"atypb7","first-page":"201","volume":"2010","author":"Bhaskara A.","year":"2010","journal-title":"STOC"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Charikar,\n                      Greedy approximation algorithms for finding dense components in a graph\n                      , in Proceedings of the Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbru\u0308cken, Germany, 2000, pp. 84-95.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"atypb9","unstructured":"E. Chlamtac, M. Dinitz, C. Konrad, G. Kortsarz, and G. Rabanca,\n                      The densest k-subhypergraph problem\n                      , in Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM 2016), LIPIcs. Leibniz Int. Proc. Inform. 60, K. Jansen, C. Mathieu, J. D. P. Rolim, and C. Umans, eds., Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, pp. 6:1-6:19."},{"key":"atypb10","first-page":"758","author":"Chlamtac E.","year":"2012","journal-title":"NJ"},{"key":"atypb11","first-page":"881","author":"Chlamta\u0301c E.","year":"2017","journal-title":"PA"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2644814"},{"key":"atypb13","unstructured":"M. Dinitz, G. Kortsarz, and Z. Nutov,\n                      Improved approximation algorithm for Steiner k-Forest with nearly uniform weights\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014), LIPIcs. Leibniz Int. Proc. Inform. 28, K. Jansen, J. D. P. Rolim, N. R. Devanur, and C. Moore, eds., Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2014, pp. 115-127."},{"key":"atypb14","first-page":"534","author":"Feige U.","year":"2002","journal-title":"ACM"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"atypb16","first-page":"468","author":"Goel A.","year":"2012","journal-title":"Japan"},{"key":"atypb17","unstructured":"A. V. Goldberg,\n                      Finding a Maximum Density Subgraph\n                      , Technical report, Berkeley, CA, 1984."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721857"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"atypb20","first-page":"637","author":"Konrad C.","year":"2013","journal-title":"Part"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and D. Peleg,\n                      On choosing a dense subgraph\n                      , in 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 692-701.","DOI":"10.1109\/SFCS.1993.366818"},{"key":"atypb22","unstructured":"A. Louis and Y. Makarychev,\n                      Approximation algorithms for hypergraph small set expansion and small set vertex expansion\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014), LIPIcs. Leibniz Int. Proc. Inform. 28, K. Jansen, J. D. P. Rolim, N. R. Devanur, and C. Moore, eds., Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2014, pp. 339-355."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"A. Louis, P. Raghavendra, and S. Vempala,\n                      The complexity of approximating vertex expansion\n                      , 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 360-369.","DOI":"10.1109\/FOCS.2013.46"},{"key":"atypb25","first-page":"954","volume":"2017","author":"Manurangsi P.","year":"2017","journal-title":"STOC"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/080729645"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1096402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:29Z","timestamp":1787317589000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1096402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1096402"],"URL":"https:\/\/doi.org\/10.1137\/16m1096402","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}