{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:27Z","timestamp":1787341107197,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges [Formula: see text] with arbitrary covering requirements [Formula: see text], the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge [Formula: see text] is considered covered by the first time when [Formula: see text] and many of its vertices appear in the ordering. We give a [Formula: see text] approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all [Formula: see text]) of Min Sum Set Cover (MSSC) studied by Feige, Lov\u00e1sz, and Tetali, and improving upon the previous best known bound of [Formula: see text] due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., [Formula: see text]) and [Formula: see text] for every edge [Formula: see text]. We give a [Formula: see text] approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best [Formula: see text] approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the [Formula: see text] norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of [Formula: see text] for all [Formula: see text], giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For [Formula: see text], this gives yet another proof of the 4 approximation for MSSC.<\/jats:p>","DOI":"10.1137\/21m1434052","type":"journal-article","created":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T14:27:07Z","timestamp":1678372027000},"page":"327-357","source":"Crossref","is-referenced-by-count":4,"title":["On Min Sum Vertex Cover and Generalized Min Sum Set Cover"],"prefix":"10.1137","volume":"52","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Michigan, Ann Arbor, MI 48109 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7174-9778","authenticated-orcid":true,"given":"Jatin","family":"Batra","sequence":"additional","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai 400005 India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Majid","family":"Farhadi","sequence":"additional","affiliation":[{"name":"Jump Trading LLC, Chicago, IL 60654 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"Y. Azar , \nI. Gamzu , and \nX. Yin , Multiple intents re-ranking, in ACM Symposium on Theory of Computing (STOC), ACM, New York, 2009, pp. 669\u2013678.","DOI":"10.1145\/1536414.1536505"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"S. Babu , \nR. Motwani , \nK. Munagala , \nI. Nishizawa , and \nJ. Widom , Adaptive ordering of pipelined stream filters, in ACM SIGMOD International Conference on Management of Data, ACM, New York, 2004, pp. 407\u2013418.","DOI":"10.1145\/1007568.1007615"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"N. Bansal , \nA. Gupta , and \nR. Krishnaswamy , A constant factor approximation algorithm for generalized min-sum set cover, in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2010, pp. 1539\u20131545, https:\/\/doi.org\/10.1137\/1.9781611973075.125.","DOI":"10.1137\/1.9781611973075.125"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"N. Bansal  and \nS. Khot , Optimal long code test with one free bit, in Foundations of Computer Science, in Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Washington, DC, 2009, pp. 453\u2013462.","DOI":"10.1109\/FOCS.2009.23"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2677"},{"key":"ref6","unstructured":"U. Barenholz , \nU. Feige , and \nD. Peleg , Improved Approximation for Min-Sum Vertex Cover, Technical report MCS06-07, Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovat, Israel, 2006."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1080\/10556780108805818"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00143-7"},{"key":"ref9","unstructured":"E. Cohen , \nA. Fiat , and \nH. Kaplan , Efficient sequences of trials, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2003, pp. 737\u2013746."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45753-4_10"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1110-5"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0978"},{"key":"ref14","series-title":"LIPIcs. Leibniz Int. Proc. Inform. 2","first-page":"199","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"Golovin D.","year":"2008"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.3.513"},{"key":"ref16","unstructured":"F. Happach , \nL. Hellerstein , and \nT. Lidbetter , A General Framework for Approximating Min Sum Ordering Problems, preprint, https:\/\/arxiv.org\/abs\/2004.05954, 2020."},{"key":"ref17","unstructured":"F. Happach  and \nA. S. Schulz , Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover, preprint, https:\/\/arxiv.org\/abs\/2001.07011, 2020."},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"R. Hassin  and \nA. Levin , An approximation algorithm for the minimum latency set cover problem, in European Symposium on Algorithms (ESA), Springer, Berlin, 2005, pp. 726\u2013733.","DOI":"10.1007\/11561071_64"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728178"},{"key":"ref20","first-page":"377","volume":"145","author":"Im S.","year":"2014","journal-title":"Math. Program."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_18"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698243"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2014.2315777"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2954930"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.6.981.24912"},{"key":"ref26","unstructured":"J. McClintock , \nJ. Mestre , and \nA. Wirth , Precedence-constrained min sum set cover, in 28th International Symposium on Algorithms and Computation, ISAAC, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 55."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"K. Munagala , \nS. Babu , \nR. Motwani , and \nJ. Widom , The pipelined set cover problem, in Proceedings of the International Conference on Database Theory, Springer, Berlin, 2005, pp. 83\u201398.","DOI":"10.1007\/978-3-540-30570-5_6"},{"key":"ref28","first-page":"1769","volume":"32","author":"Pisaruk N.","year":"1992","journal-title":"J. Comput. Math. Math. Phys."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2011.08.002"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"P. Tsaparas , \nA. Ntoulas , and \nE. Terzi , Selecting a comprehensive set of reviews, in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2011, pp. 168\u2013176.","DOI":"10.1145\/2020408.2020440"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00427-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1434052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:58Z","timestamp":1787339158000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1434052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1137\/21M1434052"],"URL":"https:\/\/doi.org\/10.1137\/21m1434052","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]}}}