betaFeedback

WorksComputer Science

Parameterized Approximation for Minimizing Uncovered Elements and Unsatisfied Constraints

Abstract

Min-UnCoverage asks for at most kk sets minimizing uncovered weight. Min-Unsat SAT and Min-Unsat CSP ask for an assignment with at most kk true variables minimizing the weight of unsatisfied clauses or constraints. For constraints of arity at most dd, we give a deterministic (1+ε)(1+\varepsilon)-approximation for weighted Min-Unsat CSP in (dk/ε)O(k)NO(1)(dk/\varepsilon)^{O(k)}N^{O(1)} time, where NN is the input size. This also gives approximation schemes for bounded-arity SAT and coverage with bounded element frequency. We show that weighted coverage with set size at most dd can be solved exactly in 2O(kd)NO(1)2^{O(kd)}N^{O(1)} time by adapting color-coding. For coverage on incidence graphs of bounded semi-ladder index, we give a deterministic parameterized approximation scheme . We show that, unless FPT=W[1]\mathrm{FPT}=\mathrm{W}[1], SAT and CSP have no finite-factor FPT approximation parameterized by k+dk+d when variable frequency is at most dd, or on K3,3K_{3,3}-free incidence graphs of semi-ladder index at most four. Known Hitting Set hardness gives the same lower bound for all three problems at VC dimension two. Under the same assumption, we show that no computable relaxation g(k,d)≥kg(k,d)\geq k allows an FPT algorithm to preserve a prescribed unsatisfied-weight target for SAT or CSP, already for arity three and, separately, bounded variable frequency. For coverage, known algorithms preserve the target using at most k+1k+1 sets on incidence graphs of bounded semi-ladder index.

Introduction

Coverage and satisfaction problems under a cardinality bound can be viewed from two complementary perspectives: maximizing the weight of the elements, clauses, or constraints that are covered or satisfied, or minimizing the weight of those that remain uncovered or unsatisfied. Because these two objective values sum to the total input weight, the formulations have the same optimal solutions. Their multiplicative approximation guarantees, however, do not translate into one another. When an optimal solution leaves only a small amount of weight uncovered or unsatisfied, a constant-factor approximation to the covered or satisfied weight may leave a residual arbitrarily larger than the optimum, whereas an approximation to the residual controls this quantity directly. Conversely, when the optimal covered or satisfied weight is small, an approximation to the residual may provide little information about the weight actually covered or satisfied, making the maximization viewpoint more informative. Thus, depending on the instance, either side of the complementary objective may provide the more meaningful approximation guarantee. While the maximization viewpoint has been studied extensively for coverage and satisfiability problems, these differences motivate a systematic study of the corresponding residual-minimization objectives under a cardinality bound.

The classical Maximum Coverage problem asks for at most kk sets whose union has maximum total weight. We study the complementary residual objective: selecting at most kk sets so as to minimize the total weight of the elements left uncovered. This objective arises naturally when the unserved portion is itself the quantity of interest. For example, under the approval-based Chamberlin–Courant rule, each candidate corresponds to the set of voters who approve that candidate. Thus, after selecting a committee, the uncovered elements correspond precisely to voters who approve none of its members [7, 31]. We call this problem Min-UnCoverage. It has previously appeared under the names MinNonCovered [31 Definition 2.2] and Min kk-Uncovered [16 Section 4.2.3]. Formally, an instance consists of a ground set UU, a family S⊆2U\mathcal{S} \subseteq2^{U}, positive rational weights on the ground elements, and a cardinality bound kk. The goal is to select at most kk sets while minimizing the total weight of the elements they leave uncovered. We study this objective together with two satisfaction analogues. An instance of Min-Unsat SAT contains a CNF formula with positive rational clause weights, and an instance of Min-Unsat CSP contains weighted constraints over Boolean variables. In both problems, the goal is to set at most kk variables to true while minimizing the total weight of the unsatisfied clauses or constraints. All weights are encoded in binary. The three problems form a hierarchy that preserves objective weights: Min-UnCoverage is the monotone special case of Min-Unsat SAT, which is a special case of Min-Unsat CSP. The cardinality bound is an upper bound throughout; the distinction from requiring exactly kk selected objects is discussed in Proposition 3.6.

For coverage, the separation between the two approximation viewpoints Maximum Coverage and Min-UnCoverage is already extreme. As Skowron and Faliszewski emphasize, when kk sets can cover the whole universe, a constant-factor approximation for Maximum Coverage may still miss a constant fraction of the elements, whereas every finite-factor approximation for Min-UnCoverage must find a complete cover [31 p. 692]. On the maximization side, the classical greedy algorithm achieves a (1−1/e)(1 - 1/e) approximation [28], and Feige proved that, for every constant δ>0\delta> 0, no polynomial-time algorithm can achieve 1−1/e+δ1 - 1/e + \delta unless P=NP\mathrm{P} = \mathrm{NP} [15]. Even allowing parameterized running time does not improve this threshold in general: under the randomized Gap Exponential Time Hypothesis (Gap-ETH), no T(k)No(k)T(k)N^{o(k)}-time algorithm achieves 1−1/e+δ1 - 1/e + \delta for any function TT and any constant δ>0\delta> 0 [25].

For the complementary minimization objectives, the obstruction is already visible when the optimum value is zero. Every approximation with a finite factor must then find a zero-valued solution exactly. Deciding whether at most kk sets cover every element, or whether an assignment of Hamming weight at most kk satisfies every constraint, is W[2]W[2]-hard by the standard hardness of Set Cover and its monotone-SAT encoding. Consequently, unless FPT = W[2], none of the three unrestricted problems admits a finite-factor FPT approximation parameterized by kk (Corollary 2.9). All objective-value hardness proofs in this paper distinguish zero optimum from positive optimum. They do not establish a multiplicative gap under the promise that the optimum is positive. This sharp contrast, together with the inapproximability of the unrestricted problems, shows that obtaining any meaningful finite-factor approximation requires imposing additional structure. This motivates our study of natural restrictions of the incidence graph under which the residual-minimization objectives become approximable.

Alongside approximating the minimum uncovered or unsatisfied weight while using at most kk selectable objects, we study a complementary question. Given a target attained by a solution using at most kk selectable objects, can an FPT algorithm preserve that target while using at most g(k,d)g(k,d) objects, where gg is a computable function of the parameters and g(k,d)≥kg(k,d) \ge k? In this setting, the maximization and residual-minimization formulations are exactly equivalent: leaving uncovered or unsatisfied weight at most tt is the same as covering or satisfying weight at least the corresponding complementary target. Thus, unlike multiplicative approximation of the objective value, there is no distinction between the two viewpoints once the target is fixed and only the cardinality bound is approximated. Consequently, any target-preserving result for one formulation immediately transfers to the other. For coverage, this is the weighted Partial Set Cover problem: given a prescribed coverage threshold, minimize the number of sets whose union has total weight at least that threshold. We return to this question after introducing the structural restrictions considered in the paper and presenting our results on approximating the uncovered or unsatisfied weight.

Structural restrictions. We study five principal restrictions on the incidence graph G=(A⊎B,E)G = (A \uplus B, E). For Min-UnCoverage, A=SA = S and B=UB = U, with Su∈ES_u \in E if and only if u∈Su \in S. For Min-Unsat SAT and Min-Unsat CSP, AA is the set of variables and BB is the set of clauses or constraints, with xC∈Ex_C \in E if and only if xx occurs in CC. Thus, the cardinality bound kk restricts the choices made on side AA, while the vertices whose weights contribute to the residual lie on side BB. The first two restrictions bound degrees on opposite sides of the incidence graph. Bounded arity means that every clause or constraint contains at most dd variables; for Min-UnCoverage, the corresponding condition is bounded element frequency, meaning that every ground element belongs to at most dd sets. Conversely, bounded variable frequency means that every variable occurs in at most dd clauses or constraints; on the coverage side, this corresponds to bounded set size. These two restrictions are incomparable.

Beyond these two one-sided degree bounds, we consider three increasingly general restrictions on the incidence graph. The first is Kd,dK_{d,d}-freeness: the incidence graph contains no complete bipartite subgraph with dd vertices on each side. A degree bound of dd on either side implies Kd+1,d+1K_{d+1,d+1}-freeness. Next, we consider bounded semi-ladder index, a notion introduced by Fabiánski et al. [14]. A semi-ladder of order ℓ\ell consists of vertices a1,…,aℓa_1,\ldots,a_\ell on one side and b1,…,bℓb_1,\ldots,b_\ell on the other such that aibia_i b_i is a nonedge and aibja_i b_j is an edge whenever j<ij < i (Definition 2.5). The semi-ladder index is the maximum order of such a pattern. Every Kd,dK_{d,d}-free graph has semi-ladder index less than 2d2d, while set systems of semi-ladder index two can contain arbitrarily large bicliques. For example, a disjoint union of complete bipartite graphs has semi-ladder index at most two and may contain a Kn,nK_{n,n} for arbitrarily large nn. Thus bounded semi-ladder index is strictly more general than biclique-freeness. The final restriction is bounded VC dimension. The neighborhoods of the vertices in AA form the set system {NG(a):a∈A}⊆2B\{N_G(a) : a \in A\} \subseteq2^B. A set X⊆BX \subseteq B is shattered if, for every Y⊆XY \subseteq X, there exists a vertex a∈Aa \in A such that NG(a)∩X=YN_G(a) \cap X = Y. The VC dimension is the maximum cardinality of a shattered set (Definition 2.4). Every shattered set of size ℓ\ell yields a semi-ladder of order ℓ\ell (Observation 2.7), so bounded semi-ladder index implies bounded VC dimension. The converse fails: half-graphs have VC dimension one but unbounded semi-ladder index; a half-graph of order ℓ\ell has vertices a1,…,aℓa_1,\ldots,a_\ell and b1,…,bℓb_1,\ldots,b_\ell, with aibja_i b_j an edge exactly when j<ij<i.

Our results. We first present our results on approximating the residual weight while respecting the cardinality bound, organized according to the hierarchy of incidence restrictions described above. We then turn to approximating the cardinality bound while preserving a prescribed upper bound on the residual weight.

Bounded arity and ground-element frequency. For every d≥1d\ge1, we give a deterministic efficient parameterized approximation scheme (EPAS) for weighted arity-dd Min-Unsat CSP parameterized by k+dk+d (Theorem 3.4). For 0<ε≤10<\varepsilon\le1, its running time is

(dk/ε)O(k)NO(1),(dk/\varepsilon)^{O(k)}N^{O(1)},

where NN denotes the input encoding size. Since CNF formulas are a special case of Boolean CSP, the same result applies to weighted arity-dd Min-Unsat SAT. Moreover, encoding each ground element as a monotone clause of the same weight gives a deterministic EPAS for weighted Min-UnCoverage when every ground element belongs to at most dd sets (Corollary 3.5). Skowron and Faliszewski previously gave a randomized FPT approximation scheme for unit weights; our algorithm is deterministic and also handles positive rational weights [31].

The algorithm compares the all-zero assignment with an optimum assignment at each recursive step. If the all-zero assignment is not already a (1+ε)(1+\varepsilon)-approximation, then some variable set to one by the optimum occurs in constraints of sufficiently large total weight that the all-zero assignment violates. Bounded arity limits the number of variables with this property, allowing the algorithm to branch over them in FPT time.

Bounded variable frequency and set size. This pair of corresponding one-sided degree restrictions yields a sharp separation between coverage and general satisfaction problems. In the monotone-CNF encoding of Min-UnCoverage, each set SS is represented by a variable xSx_S, which occurs in one clause for every element of SS. Thus, a bound of dd on set size is exactly a bound of dd on variable frequency. Bläser’s randomized color-coding algorithm gives an exact FPT algorithm for unweighted Partial Set Cover [4]; Bonnet et al. gave an alternative deterministic FPT algorithm for Maximum kk-Set Cover based on greediness-for-parameterization [13]. We adapt Bläser’s color-coding framework to positive rational element weights and show that weighted Min-UnCoverage is exactly solvable in

2O(kd)NO(1)2^{O(kd)}N^{O(1)}

time when every set has size at most dd (Proposition B.1). Our extension assigns each covered element (at most kdkd many) to one selected set, producing at most kk pairwise disjoint subsets, each of size at most dd. A kdkd-perfect hash family contains a coloring that is injective on all elements covered by an optimum solution, and a dynamic program over subsets of colors finds a maximum-weight collection of such subsets while remembering the original set containing each one. Selecting those original sets recovers an optimum coverage solution. Since this proof is a weighted deterministic adaptation of Bläser’s color-coding argument, rather than one of our main structural techniques, we defer it to Section B. In contrast, we show that unless FPT = W[1], neither Min-Unsat SAT nor Min-Unsat CSP admits a finite-factor FPT approximation parameterized by k+dk+d, even on unweighted instances in which every variable occurs in at most dd clauses or constraints (Theorem 4.6). Under the Exponential Time Hypothesis (ETH), no such approximation runs in f(k,d)No(k+d)f(k,d)N^{o(\sqrt{k+d})} time for any computable function ff.

Kd,dK_{d,d}-free graphs and bounded semi-ladder index. We now move from one-sided degree bounds to restrictions on the entire incidence graph. For weighted Min-UnCoverage on incidence graphs of semi-ladder index at most dd, we give a deterministic EPAS parameterized by k+dk+d (Theorem 5.4), with running time

(dkε)O(d2kε2log⁡2kε)NO(1).\left(\frac{dk}{\varepsilon}\right)^{O\left(\frac{d^2k}{\varepsilon^2}\log\frac{2k}{\varepsilon}\right)}N^{O(1)}.

The algorithm adapts the skeleton-based branching framework and deterministic weighted-net construction of Kundu et al. [23], which in turn builds on Guillemot’s FPT algorithm for Set Cover on semi-ladder-free hypergraphs [17]. The skeletons, eligible families, forced-coverage intersections, weighted nets, and semi-ladder depth argument are inherited from that framework. Our additional step is the residual-weight case distinction and averaging argument described next, which gives the new approximation guarantee. The algorithm maintains kk skeletons M1,…,MkM_1,\ldots,M_k, where MiM_i records elements that the iith chosen set must contain. The sets containing MiM_i remain eligible for that coordinate, and their intersection is already guaranteed to be covered. Let WW be the elements not guaranteed to be covered at any coordinate. If w(W)>(1+ε)OPT⁡miss(I)w(W)>(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I), an averaging argument shows that some optimum set OiO_i covers weight greater than δw(W)\delta w(W), where δ=ε/(k(1+ε))\delta=\varepsilon/(k(1+\varepsilon)). A weighted δ\delta-net then contains an element u∈Oi∩Wu\in O_i\cap W; since the algorithm tries every pair (i,u)(i,u), one recursive branch adds uu to the corresponding skeleton and remains consistent with the fixed optimum. Each element added to one skeleton produces a new semi-ladder rung, so every skeleton has size at most dd and the recursion depth is at most kdkd. When w(W)w(W) is small, arbitrary eligible sets already give the required approximation.

By Observation 2.6, every Kd,dK_{d,d}-free graph has semi-ladder index less than 2d2d. Consequently, Theorem 5.4 also gives an EPAS for weighted Kd,dK_{d,d}-free Min-UnCoverage. For the unit-weight case, we additionally give a specialized algorithm with the improved running time (dk/ε)O(dk)NO(1)(dk/\varepsilon)^{O(dk)}N^{O(1)} (Theorem A.5).

These graph-based positive results rely on the monotonicity of coverage and do not extend to general CNF formulas. Unless FPT = W[1], Min-Unsat SAT and Min-Unsat CSP admit no finite-factor FPT approximation even on unweighted K3,3K_{3,3}-free instances and, separately, on unweighted instances of semi-ladder index at most four (Theorem 4.3). Under ETH, no such approximation runs in f(k,d)No(k+d)f(k,d)N^{o(k+d)} time for any computable function ff.

Bounded VC dimension. We compare the preceding graph restrictions with bounded VC dimension. Badanidiyuru et al. gave an EPAS for Maximum Coverage on set systems of bounded VC dimension [3]. The corresponding residual objectives behave differently. Bringmann et al. proved that Hitting Set is W[1]-hard even when both its primal and dual VC dimensions are at most two [5]. Dualizing their instances and using the fact that any finite-factor approximation must distinguish optimum zero from positive optimum (Proposition 2.8) shows that, unless FPT = W[1], none of Min-UnCoverage, Min-Unsat SAT, and Min-Unsat CSP admits a finite-factor FPT approximation on unweighted instances of VC dimension at most two (Corollary 2.10). Thus, bounded semi-ladder index suffices for approximating the coverage residual, whereas bounded VC dimension alone does not.

Table 1 summarizes the FPT approximability landscape for the residual-minimization objective (the uncovered or unsatisfied weight) under the cardinality bound kk, with parameter k+dk+d, for each incidence restriction considered in the paper. Positive results are for positive rational weights unless stated otherwise, whereas all hardness results already hold for unweighted instances. Each hardness entry rules out every finite-factor FPT approximation parameterized by k+dk+d, unless FPT = W[1].

Incidence restrictionMin-UnCoverageMin-UnCoverage running timeMin-Unsat SAT/Min-Unsat CSP
clause or constraint arity ≤d\le d; ground-element frequency ≤d\le dConsequence: deterministic EPAS for weighted instances (Corollary 3.5); External: unit-weight randomized EPAS [31](dk/ε)O(k)NO(1)(dk/\varepsilon)^{O(k)}N^{O(1)}This paper: deterministic EPAS for weighted instances (Theorem 3.4); (dk/ε)O(k)NO(1)(dk/\varepsilon)^{O(k)}N^{O(1)}
variable frequency ≤d\le d; set size ≤d\le dAdaptation: exact FPT algorithm for weighted instances, extending [4] (Proposition B.1)2O(kd)NO(1)2^{O(kd)}N^{O(1)}This paper: no finite-factor FPT approximation (Theorem 4.6)
Kd,dK_{d,d}-free incidence graphConsequence: deterministic EPAS for weighted instances (Theorem 5.4); This paper: improved parameter dependence for unit weights (Theorem A.5)weighted: (dk/ε)O(L)NO(1)(dk/\varepsilon)^{O(L)}N^{O(1)}; unit: (dk/ε)O(dk)NO(1)(dk/\varepsilon)^{O(dk)}N^{O(1)}This paper: no finite-factor FPT approximation on unweighted K3,3K_{3,3}-free instances (Theorem 4.3)
semi-ladder index ≤d\le dThis paper: deterministic EPAS for weighted instances (Theorem 5.4)(dk/ε)O(L)NO(1)(dk/\varepsilon)^{O(L)}N^{O(1)}This paper: no finite-factor FPT approximation on unweighted instances of semi-ladder index at most four (Theorem 4.3)
VC dimension ≤d\le dConsequence: no finite-factor FPT approximation, even for d=2d=2 (Corollary 2.10, from [5])—Consequence: no finite-factor FPT approximation, even for d=2d=2 (Corollary 2.10, from [5])

Table 1. Residual-objective results for parameter k+dk+d. “This paper” marks results proved here; “Consequence” marks an immediate corollary or specialization; “Adaptation” marks a weighted deterministic extension of a cited algorithm; and “External” marks cited work. All hardness entries use the zero-optimum barrier and do not give a gap between two positive optimum values. Here NN is the input size and L=(d2k/ε)log⁡(2k/ε)L=(d^2k/\varepsilon)\log(2k/\varepsilon). In the two one-sided degree rows, the first line gives the SAT/CSP restriction and the second line gives the corresponding coverage restriction.

Approximating the cardinality bound. We finally consider relaxing the cardinality bound while preserving a prescribed upper bound on the uncovered or unsatisfied weight. As discussed above, the maximization and residual-minimization formulations are equivalent once the target is fixed. On the coverage side, Jain et al. [21] showed that, on Kd,dK_{d,d}-free incidence graphs, a target attainable with kk sets can be attained in FPT time with at most k+1k+1 sets. Kundu et al. [23] extended this additive-one guarantee to weighted Partial Set Cover on incidence graphs of bounded semi-ladder index. Their result therefore also applies to the biclique-free and one-sided degree-bounded coverage classes considered here. For bounded set size, our exact FPT algorithm attains the target without increasing the cardinality bound. In contrast, bounded VC dimension alone does not permit an additive-one guarantee: for every fixed δ>0\delta>0, Partial Set Cover admits no parameterized (2−δ)(2-\delta)-approximation of the cardinality bound, unless FPT = W[1], even on set systems of VC dimension seven [23].

References

  1. [1]Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.DOI
  2. [2]Pradeesha Ashok, Sudeshna Kolay, and Saket Saurabh. Multivariate complexity analysis of geometric red blue set cover. Algorithmica, 79(3):667–697, 2017. URL: https://doi.org/10.1007/s00453-016-0216-x, doi:10.1007/S00453-016-0216-X.
  3. [3]Ashwinkumar Badanidiyuru, Robert Kleinberg, and Hooyeon Lee. Approximating low-dimensional coverage problems. In Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry (SoCG 2012), pages 161–170, 2012. doi:10.1145/2261250.2261274.DOI
  4. [4]Markus Bläser. Computing small partial coverings. Inf. Process. Lett., 85(6):327–331, 2003. doi:10.1016/S0020-0190(02)00434-9.DOI
  5. [5]Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting set for hypergraphs of low VC-dimension. In 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:18, 2016. doi:10.4230/LIPIcs.ESA.2016.23.
  6. [6]Robert D. Carr, Srinivas Doddi, Goran Konjevod, and Madhav V. Marathe. On the red-blue set cover problem. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pages 345–353, 2000. doi:10.5555/338219.338271.
  7. [7]John R. Chamberlin and Paul N. Courant. Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3):718–733, 1983.
  8. [8]Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 72(8):1346–1367, 2006. doi:10.1016/j.jcss.2006.04.007.
  9. [9]Eden Chlamtác, Yury Makarychev, and Ali Vakilian. Approximating red-blue set cover and minimum monotone satisfying assignment. In Nicole Megow and Adam D. Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, Atlanta, Georgia, USA, September 11-13, 2023, volume 275 of LIPIcs, pages 11:1–11:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.11, doi:10.4230/LIPIcs.APPROX/RANDOM.2023.11.
  10. [10]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
  11. [11]Peter Damaschke. Pareto complexity of two-parameter FPT problems: A case study for partial vertex cover. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 110–121. Springer, 2009. doi:10.1007/978-3-642-11269-0_9.DOI
  12. [12]Édouard Bonnet, László Egri, and Dániel Marx. Fixed-parameter approximability of boolean MinCSPs. In 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:18, 2016. doi:10.4230/LIPIcs.ESA.2016.18.DOI
  13. [13]Édouard Bonnet, Vangelis Th. Paschos, and Florian Sikora. Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems. RAIRO. Theoretical Informatics and Applications, 50(3):227–240, 2016. doi:10.1051/ita/2016022.DOI
  14. [14]Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive algorithms for domination and independence. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, 2019. doi:10.4230/LIPIcs.STACS.2019.27.DOI
  15. [15]Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998. doi:10.1145/285055.285059.DOI
  16. [16]Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. doi:10.3390/a13060146.DOI
  17. [17]Sylvain Guillemot. Parameterized covering in semi-ladder-free hypergraphs. ACM Transactions on Computation Theory, 17(2):9:1–9:15, 2025. doi:10.1145/3708510.DOI
  18. [18]Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory of Computing Systems, 41(3):501–520, 2007. doi:10.1007/s00224–007–1309–3.DOI
  19. [19]Tanmay Inamdar, Pallavi Jain, Daniel Lokshтанov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 88:1–88:18, 2024. doi:10.4230/LIPIcs.ICALP.2024.88.DOI
  20. [20]Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. FPT approximations for connected maximum coverage. CoRR, abs/2601.08639, 2026. URL: https://doi.org/10.48550/arXiv.2601.08639, arXiv:2601.08639, doi:10.48550/ARXIV.2601.08639.
  21. [21]Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized approximation schemes for biclique-free max k-weight SAT and max coverage. ACM Transactions on Algorithms, 22(1):3:1–3:30, 2026. doi:10.1145/3763238.
  22. [22]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Flow-augmentation III: Complexity dichotomy for boolean CSPs parameterized by the number of unsatisfied constraints. SIAM Journal on Computing, 54(4):1065–1137, 2025. doi:10.1137/23M1553698.DOI
  23. [23]Madhumita Kundu, Souvik Saha, Saket Saurabh, and Anannya Upasana. Fixed budget vs. covering target: The partial set cover boundary for bounded VC-dimension, 2026. URL: https://arxiv.org/abs/2608.03801, arXiv:2608.03801, doi:10.48550/arXiv.2608.03801.
  24. [24]Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717–729, 2005. doi:10.1007/s00454-004-1108-4.
  25. [25]Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 62–81, 2020. doi:10.1137/1.9781611975994.5.DOI
  26. [26]Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: Greedy strikes back. Theoretical Computer Science, 1028:115033, 2025. doi:10.1016/j.tcs.2024.115033.DOI
  27. [27]Pauli Miettinen. On the positive-negative partial set cover problem. Information Processing Letters, 108(4):219–221, 2008. doi:10.1016/j.ipl.2008.05.007.DOI
  28. [28]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming, 14:265–294, 1978. doi:10.1007/BF01588971.DOI
  29. [29]David Peleg. Approximation algorithms for the label-covermax and red-blue set cover problems. J. Discrete Algorithms, 5(1):55–64, 2007. URL: https://doi.org/10.1016/j.jda.2006.03.008, doi:10.1016/J.JDA.2006.03.008.
  30. [30]Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 373–387, 2012. doi:10.1137/1.9781611973099.33.DOI
  31. [31]Piotr Skowron and Piotr Faliszewski. Chamberlin–Courant rule with approval ballots: Approximating the MaxCover problem with bounded frequencies in FPT time. Journal of Artificial Intelligence Research, 60:687–716, 2017. doi:10.1613/jair.5628.DOI
  32. [32]V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264–280, 1971. doi:10.1137/1116025.DOI

Paper details

vlnc:W_586ftr3r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents