2026-07-20T11:15:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8264 2024-03-06T10:41:52Z ddc:004 open_access

Precedence-Constrained Min Sum Set Cover McClintock, Jessica Mestre, Julián Wirth, Anthony planted dense subgraph min sum set cover precedence constrained We introduce a version of the Min Sum Set Cover (MSSC) problem in which there are "AND" precedence constraints on the m sets. In the Precedence-Constrained Min Sum Set Cover (PCMSSC) problem, when interpreted as directed edges, the constraints induce an acyclic directed graph. PCMSSC models the aim of scheduling software tests to prioritize the rate of fault detection subject to dependencies between tests. Our greedy scheme for PCMSSC is similar to the approaches of Feige, Lovasz, and, Tetali for MSSC, and Chekuri and Motwani for precedence-constrained scheduling to minimize weighted completion time. With a factor-4 increase in approximation ratio, we reduce PCMSSC to the problem of finding a maximum-density precedence-closed sub-family of sets, where density is the ratio of sub-family union size to cardinality. We provide a greedy factor-sqrt m algorithm for maximizing density; on forests of in-trees, we show this algorithm finds an optimal solution. Harnessing an alternative greedy argument of Chekuri and Kumar for Maximum Coverage with Group Budget Constraints, on forests of out-trees, we design an algorithm with approximation ratio equal to maximum tree height. Finally, with a reduction from the Planted Dense Subgraph detection problem, we show that its conjectured hardness implies there is no polynomial-time algorithm for PCMSSC with approximation factor in O(m^{1/12-epsilon}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jessica McClintock and Julián Mestre and Anthony Wirth 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.55 urn:nbn:de:0030-drops-82648 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.55 eng https://creativecommons.org/licenses/by/3.0/legalcode