Pith. sign in

REVIEW 3 major objections 3 minor 147 references

Bounded VC-dimension makes fixed-budget Maximum Coverage tractable, but the target-covering version Partial Set Cover stays hard: under FPT≠W[1] it has no FPT (2−δ)-approximation even at VC-dimension 7, and under ETH no parameterized approx

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Partial Set Cover is inapproximable below factor 2 even at VC-dimension 7, while bounded semi-ladder index restores a k+1-sets covering target and yields new EPAS results.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection A serious, dense theory paper that likely resolves the target-covering boundary for bounded VC-dimension; the lower-bound half leans on two very strong black-box theorems that need referee verification, but the internal reductions are sound. the 3 major comments →

arxiv 2608.03801 v1 pith:EXUQSZID submitted 2026-08-04 cs.DS

Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension

Madhumita Kundu , Souvik Saha , Saket Saurabh , Anannya Upasana This is my paper
classification cs.DS MSC 68Q2768W2568Q1705C65
keywords Partial Set CoverMaximum CoverageVC-dimensionparameterized approximationEPASsemi-ladder indexdownward intersection complexityCC-MaxSAT
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper draws a sharp structural boundary between the two parameterized covering objectives at bounded VC-dimension. For the fixed-budget objective, Maximum Coverage, bounded VC-dimension supports efficient parameterized approximation schemes. For the target-covering objective, Partial Set Cover, the same structure fails: assuming FPT≠W[1], no FPT algorithm approximates within factor below 2, even on VC-dimension-7 instances, and under ETH there is no parameterized approximation scheme there and no 2^{o(d)}-approximation at VC-dimension d. The paper then shows that the stronger hypothesis of bounded semi-ladder index restores the target guarantee: if k sets cover weight W, a randomized FPT algorithm finds k+1 sets covering weight W in time 2^{O(Γk log k)} times the input size. This locates the boundary fairly precisely: bounded VC-dimension alone is enough for budgeted coverage, but target covering needs the extra semi-ladder structure.

Core claim

The central claim is that for parameterized approximation, bounded VC-dimension is the right regime for fixed-budget Maximum Coverage but provably not for target-covering Partial Set Cover. The lower-bound half shows that all three target-covering barriers occur at tiny VC-dimension: a row-and-blocking-list reduction from the constant-factor inapproximability of k-Clique rules out (2−δ)-approximation at VC-dimension 7; a regular low-soundness 2-CSP reduction rules out a PAS under ETH at VC-dimension 7; and a list version raises VC-dimension only logarithmically in the ratio, ruling out 2^{o(d)}-approximation at VC-dimension d. The algorithmic half identifies bounded semi-ladder index, a para

What carries the argument

The central objects are the semi-ladder and the closely related downward intersection complexity Γ of the incidence bipartite graph. A semi-ladder is a two-sided sequence of red vertices r_1,…,r_d and blue vertices b_1,…,b_d with edges (r_i,b_j) exactly when i>j and missing diagonal edges (r_i,b_i); Γ measures the length of chains of realizable subsets and differs from the semi-ladder index by at most one. The lower bounds use a synthetic row-and-blocking-list syntax: each element is sensitive to at most two positions and each sensitivity is blocked by at most q labels, and a trace bound on such q-local set systems caps the VC-dimension automatically. The algorithms maintain k MustInclude sk

Load-bearing premise

The lower-bound half imports two black-box hardness theorems — constant-factor FPT inapproximability of k-Clique and an ETH-hard regular low-soundness 2-CSP gap with running time F(k)|Σ|^{k/log^{Cζ} k} — and if either stated gap or running-time exponent is weaker than cited, the main separation theorems weaken or fall; the deterministic half additionally assumes an FPT Dominating Set algorithm whose exact running time is never stated.

What would settle it

Run the Section 3.1 row-and-blocking-list construction on a sequence of graphs H with no k-clique and check whether any FPT algorithm can distinguish Partial Set Cover instances with optimum at most k from those with optimum greater than (2−δ)k, all having VC-dimension at most 7. Producing such an algorithm, or a correct (2−δ)-approximation for VC-dimension-7 Partial Set Cover, would directly falsify the main separation.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Target-covering is intrinsically harder than budgeted coverage under bounded VC-dimension: no EPAS, no PAS, and no factor-2 FPT approximation can be built on VC-dimension alone.
  • On bounded semi-ladder index instances, Weighted Partial Set Cover gets a randomized additive guarantee: k+1 sets instead of k, with the same weight W, in FPT time 2^{O(Γk log k)}N, and this yields a PAS for the partial-cover version.
  • Weighted CC-MaxSAT inherits an EPAS at bounded semi-ladder index and, via the improved deterministic trace-enumerated implementation of the bounded-VC Maximum Coverage scheme, an EPAS at bounded VC-dimension with running time 2^{O~(kd/ε)}N^{O(1)}.
  • The same branching framework extends to per-class coverage targets and matroid independence constraints, covering partial dominating set, geometric partial covering, and bounded-size covering problems.
  • Deterministic counterparts exist through weighted δ-nets of size O((Γ/δ) log(1/δ)), giving deterministic EPAS/PAS with the same structural parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The row-and-blocking-list method gives a reusable template for proving target-side hardness while keeping VC-dimension constant, so other fixed-budget versus target-covering pairs (influence, clustering, or domination variants) may display the same split.
  • The (2−δ) barrier is left open at intermediate dimensions: the paper rules out approximation below 2 at dimension 7, but does not construct instances showing that factor 2 itself is achievable there.
  • Because the semi-ladder index is a single numeric parameter, one could investigate intermediate regimes where Γ is large but not unbounded, asking whether running time degrades smoothly with Γ.
  • The improved trace-enumeration insight is independent of the target-covering question and may speed up other reductions that call the bounded-VC Maximum Coverage scheme as a subroutine.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the parameterized approximability of Maximum Coverage (fixed budget) versus Partial Set Cover (covering target) on set systems of bounded VC-dimension. Its central negative claim is that bounded VC-dimension does not support target-covering algorithms: assuming FPT != W[1], Partial Set Cover has no FPT (2-delta)-approximation even at VC-dimension 7; assuming ETH, it has no PAS at VC-dimension 7 and no 2^{o(d)}-approximation at VC-dimension d. These results are proved by reductions from Lin's k-Clique inapproximability and a regular low-soundness 2-CSP hardness of Bafna--Karthik--Minzer, using a unified rows-and-blocking-lists construction that yields the VC-dimension bounds. On the positive side, the paper introduces the semi-ladder index / downward intersection complexity Gamma as the right structural parameter: for Weighted Max RBDS it gives a randomized EPAS in (1/epsilon)^{O(Gamma k log k)} ||G|| time, and for Dec-Wt-Partial RBDS it gives an additive approximation that finds k+1 sets covering weight W whenever k sets can, in 2^{O(Gamma k log k)} ||G|| time. It further extends the framework to matroid/partition constraints, gives a deterministic FPT reduction from Weighted CC-MaxSAT to Weighted Maximum Coverage, and proposes a faster deterministic implementation of the BKL bounded-VC scheme.

Significance. If the two imported hardness theorems are exactly as quoted, the negative separation is a significant conceptual contribution: it shows that the EPAS for fixed-budget Maximum Coverage at bounded VC-dimension does not carry over to the target-covering objective. The positive framework is also substantial: it strictly generalizes the earlier K_{d,d}-free results, handles weights directly, and uses a clean skeleton/MustInclude invariant in which the downward intersection complexity bounds the recursion depth. The internal reductions and the main randomized algorithm are coherent, and the approximation factors and running times are derived rather than fitted, so the paper is not circular. The deterministic results and the improved BKL implementation extend the reach of the framework, although they rely on an external FPT Dominating Set subroutine whose running time is not stated.

major comments (3)
  1. [Sec. 3, Prop. 3.3 and 3.7 (Theorems 3.6, 3.10, 3.13, 3.14)] The four lower-bound theorems are conditional on the exact statements of [Lin21, Thm 1.2] and [BSM25, Thm 1.1], paraphrased in Propositions 3.3 and 3.7. The internal reductions are coherent, but the hypotheses are load-bearing: Theorem 3.6 needs Lin's theorem to exclude F(k)n^a for every constant a and every fixed delta, while Theorems 3.10/3.13/3.14 need the BSM theorem with soundness zeta arbitrarily close to 1, running time F(k)|Sigma|^{k/log^{C_zeta} k}, and constant regularity D_zeta. If the source theorems have additional restrictions or different gap/runtime constants, the claimed (2-delta), no-PAS, and 2^{o(d)} conclusions weaken or fail. Please state the source theorems in full (ideally verbatim) and confirm that all parameters used here are covered by those statements.
  2. [Sec. 8, Lemma 2.5 and deterministic algorithms] The deterministic results (Theorem 1.5 and the Section 8 framework) invoke an FPT algorithm for Dominating Set on semi-ladder-free graphs [Gui25] without stating its running time. The claims such as '(k log k / epsilon)^{O(k)} * 2^{O~(kd/epsilon)} ||I||^{O(1)}' cannot be reproduced from this paper alone. Please give the exact running time of the dominating-set subroutine, state how it is combined with the weighted delta-net construction (Lemma 2.5), and derive the final deterministic bounds. Without this, the deterministic EPAS for CC-MaxSAT and the improved deterministic BKL implementation cannot be checked.
  3. [Sec. 7, Lemma 7.6, base case] In the base case where mu(J)=0, the proof argues that if u in N(s_alpha) and u not in FreeCov_alpha, then DI(G, MustInclude_alpha cup {u}) >= Gamma+1 by Lemma 7.5. However, Lemma 7.5 has the hypothesis u in B \ FreeCov(J), not merely u not in FreeCov_alpha. The gap is fixable: apply Lemma 7.5 only when u not in FreeCov(J); if u belongs to another FreeCov_beta, it is already covered by every consistent tuple and no contradiction is needed. Please correct this step, since the current proof does not establish the base case as written.
minor comments (3)
  1. [Sec. 2.2.1 / Theorem 1.2] The proof gives success probability per run (epsilon/(2k))^{O(Gamma k)} and hence a running-time bound (2k/epsilon)^{O(Gamma k)} poly(||G||), which is (1/epsilon)^{O(Gamma k)} 2^{O(Gamma k log k)}. Stating Theorem 1.2 as (1/epsilon)^{O(Gamma k log k)} ||G|| is an overestimate; please align the displayed running time with the proof.
  2. [Sec. 5, Definition 5.5] The definition of DI(G, X) for X subseteq B uses chains of realizable sets but does not say what happens when X = emptyset or when IntExt(G, X) = emptyset; this leads to minor ambiguity in the proof of Lemma 5.7. A short convention would help.
  3. [Throughout] There are several typos and minor wording issues: 'conludes' in Lemma 2.2, 'suffice' in the introduction, and occasional 'we have'/'it holds' repetitions in Sections 6 and 7. A proofreading pass is needed.

Circularity Check

0 steps flagged

No significant circularity: the derivation chain is either self-contained or rests on independent external hardness/algorithmic results.

full rationale

The paper's central claims are not circular. The lower bounds reduce from two external hardness theorems (Lin's parameterized k-Clique inapproximability and BSM's ETH-hard regular 2-CSP) via explicit row-and-blocking-list constructions; the VC-dimension cap is proven by a trace-counting lemma, and the soundness arguments translate the imported gaps into the claimed Partial Set Cover gaps. These are reductions, not redefinitions or fitted predictions. The algorithmic side is similarly self-contained: the randomized branching algorithm maintains skeleton sets whose growth is bounded by a semi-ladder invariant (Lemma 2.2), and the downward intersection complexity DI(G) is not an ad hoc measure—it is proven within an additive constant of the pre-existing semi-ladder index (Theorem 5.9). The additive target-covering result calls the independently proven fixed-budget EPAS as a subroutine, and the deterministic section relies on standard external tools (weighted δ-nets, known Dominating Set algorithms). The only noteworthy weakness is that the deterministic running-time claims depend on cited Dominating Set algorithms whose exact running times are not restated, but this is an external-support/completeness issue, not circularity. No fitted constant is renamed as a prediction, and no load-bearing argument reduces to a self-citation chain.

Axiom & Free-Parameter Ledger

4 free parameters · 9 axioms · 1 invented entities

The central claims rest on two external complexity assumptions (FPT != W[1], ETH), two imported black-box hardness theorems whose exact statements are load-bearing (Lin's k-Clique gap; BSM's regular 2-CSP), and a set of standard tools (Sauer-Shelah, delta-nets, matroid representative families). No parameters are fitted to data; the constants q, alpha, gamma, K are proof-determined choices. The new quantity DI(G) is a defined graph parameter, bounded by the pre-existing semi-ladder index within an additive constant, and the algorithms' dependence on it is proved rather than postulated.

free parameters (4)
  • q (list-construction blocking-list length) = q = smallest integer > 4(rho-1)
    Chosen by hand in Theorem 3.13 so that the decoded assignment satisfies more than 1/(2q^2) of the constraints, beating the 1/(4q^2) soundness; not fitted to data.
  • alpha (label-selection gap) = alpha = eta/4 = (1-zeta)/4
    Gap parameter in Theorem 3.10; any value below eta/2 works, so no fitting occurs.
  • gamma (Theorem 3.14 exponent constant) = any gamma with gamma*C <= 1/4
    Chosen small enough so that 2^{gamma d_q} <= rho_q; only existence matters.
  • K (weight-scaling factor) = K = epsilon * Wmax / n
    Scaling in the weighted-to-unweighted reduction (Section 2.2.3); derived so the rounding loss is at most epsilon*OPT.
axioms (9)
  • domain assumption FPT != W[1]
    Assumed for Theorem 3.6 (no (2-delta)-approximation in FPT time); standard complexity assumption stated in the paper.
  • domain assumption ETH
    Assumed for Theorems 3.10, 3.13 and 3.14; stated in the paper.
  • domain assumption Lin's constant-factor FPT inapproximability of k-Clique ([Lin21, Theorem 1.2])
    Imported as Proposition 3.3; the exact gap formulation (omega >= k vs omega < delta k) is load-bearing for Theorem 3.6 and is not re-proved.
  • domain assumption Bafna, Karthik, Minzer regular low-soundness 2-CSP hardness under ETH ([BSM25, Theorem 1.1])
    Imported black-box with runtime F(k)|Sigma|^{k/log^{C_zeta} k} and D_zeta-regularity; load-bearing for Theorems 3.10, 3.13, 3.14.
  • domain assumption Existence of FPT algorithm for Dominating Set on d-semi-ladder-free graphs (Guillemot)
    Used in Section 8 for deterministic weighted delta-net computation; exact running time is not restated in this paper.
  • standard math Weighted delta-net theorem for bounded-VC-dimension set systems (HW86, BEHW86)
    Used for Lemma 2.5 and the derandomization in Section 8.
  • standard math Sauer-Shelah lemma
    Used in Section 9 to bound the number of realized traces in the improved BKL implementation.
  • domain assumption Representative families in matroids (Lemma 4.1, cited to IJL+24)
    Used for the matroid-constrained coverage extension (Theorem 1.6); cited rather than proved.
  • standard math Matroid contraction yields a matroid (Schrijver)
    Used in Section 12 for the matroid-constrained algorithms.
invented entities (1)
  • downward intersection complexity DI(G) (and its twin, the semi-ladder index) independent evidence
    purpose: Quantifies the recursion depth of the MustInclude branching: every skeleton set of size ell certifies a semi-ladder of order ell, so the depth is at most k * DI(G); all positive running times are stated in terms of it.
    DI(G) is a precisely defined graph parameter, bounded within an additive constant by the semi-ladder index (Theorem 5.9), which is itself a notion defined in prior literature (FPST19) and connected to the epsilon-scatter dimension of ABB+23 and BP25; the theorems' running times depend on it, giving an external falsifiable handle.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension." pith.science (2026). https://pith.science/paper/EXUQSZID

@misc{pith2026260803801,
  author       = {Pith},
  title        = {Pith review of: Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EXUQSZID}},
  note         = {Machine review of arXiv:2608.03801}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget $k$ and maximizes coverage; the latter meets a target with as few sets as possible. Badanidiyuru, Kleinberg, and Lee (SoCG 2012) give an EPAS for the former on bounded-VC set systems, while Jain et al. (SODA 2023) show that on $K_{d,d}$-free incidence graphs, $k+1$ sets suffice whenever $k$ sets meet the target. We ask whether this guarantee extends to all bounded-VC set systems. Our first result is negative. Unless FPT = W[1], Partial Set Cover admits no parameterized $(2-\delta)$-approximation even at VC-dimension seven. Under ETH, it has no parameterized approximation scheme there and no $2^{o(d)}$-approximation at VC-dimension $d$. On the positive side, bounded semi-ladder index restores this guarantee. It is stronger than bounded VC-dimension but strictly generalizes the $K_{d,d}$-free setting. For Weighted Partial Set Cover, if $k$ sets cover weight $W$, we find $k+1$ sets covering weight $W$ in $2^{O(\Gamma k\log k)}N$ time, where $\Gamma$ is the downward intersection complexity and $N$ is the input size. The framework supports per-class targets and matroid independence, with applications to partial dominating set and geometric and bounded-size covering. Finally, we give a deterministic FPT reduction from Weighted CC-MaxSAT to a bounded family of Weighted Maximum Coverage instances, preserving incidence structure and approximation schemes with constant-factor accuracy loss. This gives an EPAS at bounded semi-ladder index. We improve the deterministic BKL bounded-VC implementation; combined with our reduction, it yields a $2^{\widetilde{O}(kd/\varepsilon)}N^{O(1)}$-time EPAS for bounded-VC Weighted CC-MaxSAT.

Figures

Figures reproduced from arXiv: 2608.03801 by Anannya Upasana, Madhumita Kundu, Saket Saurabh, Souvik Saha.

Figure 1
Figure 1. Figure 1: A semi-ladder of order 5. and show that on this class the fixed-budget coverage guarantee lifts to the target-covering objective: if k sets meet the target, then one can find k + 1 sets that meet the same target. Biclique-freeness is a strict strengthening of bounded VC-dimension, so this result sits safely on the tractable side of the boundary above. We note that this biclique-free line of work appears to… view at source ↗
Figure 2
Figure 2. Figure 2: Structural hierarchy of set systems via their incidence bipartite graph. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The clique construction. Rows represent the [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The label selection construction. Rows correspond to variables and columns to labels; [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The list construction with parameter q. For a constraint e = xixj , each element ue,A,B corresponds to two lists A, B ⊆ Σ of size at most q with (A × B) ∩ Re = ∅. It is contained in the sets of rows i and j whose labels lie outside A and B, respectively, and therefore blocks the simultaneous selection of labels contained in these two lists. Proof. For completeness, let σ satisfy every constraint and select… view at source ↗
Figure 6
Figure 6. Figure 6: A semi-ladder of order 5. Square vertices induce a K2,2 To formally define the complexity measure used to upper bound the running time of our algorithms, we first introduce a few additional definitions. These are inspired by the notion of e-chains in intersection-closed hypergraphs, as introduced by Guillemot [Gui25]. Definition 5.2. Given a bipartite graph G = (R ∪ B, E) and a subset X ⊆ B we define, Incl… view at source ↗
Figure 7
Figure 7. Figure 7: realizable sets X1 ) X2 ) X3 and corresponding realizing sets Y1 ( Y2 ( Y3 [PITH_FULL_IMAGE:figures/full_fig_p040_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: 3 sized corresponding semi ladder of λ = 4 realizable sets [PITH_FULL_IMAGE:figures/full_fig_p041_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Potential Solution Family, Free Coverage and Must Include for one coordinate Definition 6.1 (Potential, Freely Covered and Non-Free neighbors). Let J = (G = (R ∪ B, E),MI = ⟨MustInclude1, . . . , MustIncludek⟩, Free, ε), be an instance for Algorithm 2. Then, the potential solution family, the set of freely covered, newly-free and non-free neighbors of any subset of B are defined as follows. 1. PotentialSol… view at source ↗
Figure 10
Figure 10. Figure 10: A visual representation of Lemma 6.3 2) Size Equality: |N ⋆ (S[↑ α, v],J )| = |N ⋆ (S,J ′ )|+|NewlyFree(J )|+|N(v)\(Free(J )∪NewlyFree(J ))|. (4) 3) Pairwise Disjoint: Each of the sets A1 = N ⋆ (S,J ′ ), A2 = NewlyFree(J ) and A3 = N(v) \ (Free(J )∪ NewlyFree(J )) are pairwise disjoint. Furthermore, N ⋆ (S[↑ α, v],J ) = S3 i=1 Ai. For ease of understanding, refer to [PITH_FULL_IMAGE:figures/full_fig_p047… view at source ↗
Figure 11
Figure 11. Figure 11: A visual respresentation of Lemma 6.4 Proof. Let S = ⟨s1, . . . , sk⟩ be a consistent tuple for J ′ . 1) Consistent: We aim to show that S is a consistent tuple for J . Since S is a consistent tuple for J ′ , for any i ∈ [k] \ {β}, we have that FreeCovi(J ′ ) ⊆ N(si)(by definition). Further by property of J and J ′ , for every i ∈ [k] \ β, we have that MustIncludei(J ) = MustIncludei(J ′ ) ⊆ N(si) which i… view at source ↗
Figure 12
Figure 12. Figure 12: Representing Case B Let S be a consistent tuple for J ′ returned in Line 12 of the algorithm. Then by Lemma 6.3, we know that S[↑ α, h⋆ ] is a consistent tuple for J . Next, we show that it also satisfies the approximation guarantee. That is, we need to show that |N ⋆ (S[↑ α, h⋆ ],J )| ≥ (1 − ε)OPT(J ). As a step toward our proof, we first establish that µ(J ′ ) < µ(J ), allowing us to apply the induction… view at source ↗
Figure 13
Figure 13. Figure 13: A diagram illustrating the interaction between [PITH_FULL_IMAGE:figures/full_fig_p054_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Representing Case C and let J ′ denote the instance (G = (R ∪ B, E),MI′ , Free(J ) ∪ NewlyFree ∪ {u}, ε) where MI′ = ⟨MustInclude1, . . . , MustIncludeα ∪ {u}, . . . , MustIncludek⟩ which the algorithm recursively solves in this branch. Let S be a consistent tuple for J ′ , then due to Lemma 6.4, S is also a consistent tuple for J . Next, we show that it also satisfies the approximation guarantee. That is… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

147 extracted references · 46 canonical work pages · 2 internal anchors

  1. [1]

    Parameterized approximation schemes for clustering with general norm objectives

    Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, D \' a niel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 202...

    2023

  2. [2]

    Fomin, and Saket Saurabh

    Omid Amini, Fedor V. Fomin, and Saket Saurabh. Implicit branching and parameterized partial cover problems. J. Comput. Syst. Sci. , 77(6):1159--1171, 2011

    2011

  3. [3]

    Global cardinality constraints make approximating some max-2-csps harder

    Per Austrin and Aleksa Stankovic. Global cardinality constraints make approximating some max-2-csps harder. In Dimitris Achlioptas and L \' a szl \' o A. V \' e gh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, M...

    2019

  4. [4]

    Using homogeneous weights for approximating the partial cover problem

    Reuven Bar - Yehuda. Using homogeneous weights for approximating the partial cover problem. J. Algorithms , 39(2):137--144, 2001

    2001

  5. [5]

    Bshouty and Lynn Burroughs

    Nader H. Bshouty and Lynn Burroughs. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In Michel Morvan, Christoph Meinel, and Daniel Krob, editors, STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings , volume 1373 of ...

    1998

  6. [6]

    Product range spaces, sensitive sampling, and derandomization

    Herv \' e Br \" o nnimann, Bernard Chazelle, and Jir \' Matousek. Product range spaces, sensitive sampling, and derandomization. SIAM J. Comput. , 28(5):1552--1575, 1999

    1999

  7. [7]

    u rgen Perl, editors, Proceedings of the WG '83, International Workshop on Graphtheoretic Concepts in Computer Science, June 16-18, 1983, Haus Ohrbeck, near Osnabr \

    Reuven Bar - Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted vertex cover problem. In Manfred Nagl and J \" u rgen Perl, editors, Proceedings of the WG '83, International Workshop on Graphtheoretic Concepts in Computer Science, June 16-18, 1983, Haus Ohrbeck, near Osnabr \" u ck, Germany , pages 17--28. Universit \" a tsverlag...

    1983

  8. [8]

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Classifying learnable geometric concepts with the vapnik-chervonenkis dimension (extended abstract). In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA , pages 273--282. ACM , 1986

    1986

  9. [9]

    Goodrich

    Herv \' e Br \" o nnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discret. Comput. Geom. , 14(4):463--479, 1995

    1995

  10. [10]

    Optimal long code test with one free bit

    Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, 2009 , pages 453--462. IEEE Computer Society, 2009

    2009

  11. [11]

    Approximating low-dimensional coverage problems

    Ashwinkumar Badanidiyuru, Robert Kleinberg, and Hooyeon Lee. Approximating low-dimensional coverage problems. In Tamal K. Dey and Sue Whitesides, editors, Proceedings of the 28th ACM Symposium on Computational Geometry, Chapel Hill, NC, USA, June 17-20, 2012 , pages 161--170. ACM , 2012

    2012

  12. [12]

    Improved approximation algorithms for max-2sat with cardinality constraint

    Markus Bl \" a ser and Bodo Manthey. Improved approximation algorithms for max-2sat with cardinality constraint. In Prosenjit Bose and Pat Morin, editors, Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings , volume 2518 of Lecture Notes in Computer Science , pages 187--198. Springer, 2002

    2002

  13. [13]

    Bounding -scatter dimension via metric sparsity

    Romain Bourneuf and Marcin Pilipczuk. Bounding -scatter dimension via metric sparsity. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 3155--3171. SIAM , 2025

    2025

  14. [14]

    S., and Dor Minzer

    Mitali Bafna, Karthik C. S., and Dor Minzer. Near optimal constant inapproximability under ETH for fundamental problems in parameterized complexity. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 2118--2129, 2025

    2025

  15. [15]

    Tight FPT approximations for k-median and k-means

    Vincent Cohen - Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece , volume 132 of LIPIcs...

    2019

  16. [16]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition . Springer, 2008

    2008

  17. [18]

    A threshold of ln n for approximating set cover

    Uriel Feige. A threshold of ln n for approximating set cover. J. ACM , 45(4):634--652, 1998

    1998

  18. [19]

    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

    2020

  19. [20]

    Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh

    Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential algorithms for partial cover problems. Inf. Process. Lett. , 111(16):814--818, 2011

    2011

  20. [22]

    Progressive algorithms for domination and independence

    Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive algorithms for domination and independence. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany , volume 126 of LIPIcs , pages 27:1--27:16. Schloss...

    2019

  21. [23]

    An extremal problem for two families of sets

    Peter Frankl. An extremal problem for two families of sets. Eur. J. Comb. , 3(2):125--127, 1982

    1982

  22. [24]

    More efforts towards fixed-parameter approximability of multiwinner rules

    Sushmita Gupta, Pallavi Jain, Souvik Saha, Saket Saurabh, and Anannya Upasana. More efforts towards fixed-parameter approximability of multiwinner rules. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025 , pages 3891--3899. ijcai.org, 2025

    2025

  23. [25]

    Approximation algorithms for partial covering problems

    Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. J. Algorithms , 53(1):55--84, 2004

    2004

  24. [26]

    Parameterized complexity of vertex cover variants

    Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory Comput. Syst. , 41(3):501--520, 2007

    2007

  25. [27]

    Parameterized covering in semi-ladder-free hypergraphs

    Sylvain Guillemot. Parameterized covering in semi-ladder-free hypergraphs. ACM Trans. Comput. Theory , 2025

    2025

  26. [28]

    Golovach and Yngve Villanger

    Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Dani \" e l Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers , volume 5344 of Lecture No...

    2008

  27. [29]

    Hochbaum

    Dorit S. Hochbaum. Approximation algorithms for np-hard problems. SIGACT News , 28(2):40--52, 1997

    1997

  28. [30]

    Hochbaum

    Dorit S. Hochbaum. The t -vertex cover problem: Extending the half integrality framework with budget constraints. In Klaus Jansen and Dorit S. Hochbaum, editors, Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings , volume 1444 of Lecture Notes in Computer Science , pag...

    1998

  29. [31]

    An approximation algorithm for MAX-2-SAT with cardinality constraint

    Thomas Hofmeister. An approximation algorithm for MAX-2-SAT with cardinality constraint. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings , volume 2832 of Lecture Notes in Computer Science , pages 301--312. Springer, 2003

    2003

  30. [32]

    Geometric Approximation Algorithms

    Sariel Har-peled. Geometric Approximation Algorithms . American Mathematical Society, USA, 2011

    2011

  31. [33]

    Epsilon-nets and simplex range queries

    David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. In Alok Aggarwal, editor, Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, Yorktown Heights, NY, USA, June 2-4, 1986 , pages 61--71. ACM , 1986

    1986

  32. [34]

    Satisfiability to coverage in presence of fairness, matroid, and global constraints

    Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2...

    2024

  33. [35]

    Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage

    Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25...

    2023

  34. [36]

    Extremal Combinatorics - With Applications in Computer Science

    Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2011

    2011

  35. [37]

    Intersection patterns of convex sets

    Gil Kalai. Intersection patterns of convex sets. Israel Journal of Mathematics , 48:161--174, 1984

    1984

  36. [38]

    V. S. Anil Kumar, Sunil Arya, and H. Ramesh. Hardness of set cover with intersection 1. In Ugo Montanari, Jos \' e D. P. Rolim, and Emo Welzl, editors, Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings , volume 1853 of Lecture Notes in Computer Science , pages 624--635. Springer, 2000

    2000

  37. [39]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montr \' e al, Qu \' e bec, Canada, May 21-24, 2002 , page 25. IEEE Computer Society, 2002

    2002

  38. [40]

    Covering many (or few) edges with k vertices in sparse graphs

    Tomohiro Koana, Christian Komusiewicz, Andr \' e Nichterlein, and Frank Sommer. Covering many (or few) edges with k vertices in sparse graphs. In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference) , volume 219 of LIPI...

    2022

  39. [41]

    Karthik C. S. , Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM , 66(5):33:1--33:38, 2019

    2019

  40. [42]

    Almost tight bounds for -nets

    J \'a nos Koml \'o s, J \'a nos Pach, and Gerhard Woeginger. Almost tight bounds for -nets. Discrete & Computational Geometry , 7(2):163--173, 1992

    1992

  41. [43]

    Vertex cover might be hard to approximate to within 2-epsilon

    Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. , 74(3):335--349, 2008

    2008

  42. [44]

    Constant approximating k-clique is w[1]-hard

    Bingkai Lin. Constant approximating k-clique is w[1]-hard. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1749--1756. ACM , 2021

    2021

  43. [45]

    Covering things with things

    Stefan Langerman and Pat Morin. Covering things with things. Discret. Comput. Geom. , 33(4):717--729, 2005

    2005

  44. [46]

    Daniel Lokshtanov, Fahad Panolan, and M. S. Ramanujan. Backdoor sets on nowhere dense SAT . In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France , volume 229 of LIPIcs , pages 91:1--91:20. Schloss Dagstuhl - Leibniz-Zentrum f...

    2022

  45. [47]

    Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 224--237. ACM , 2017

    2017

  46. [48]

    A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation

    Pasin Manurangsi. A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA , volume 69 of OASIcs , pages 15:1--15:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Info...

    2019

  47. [49]

    Tight running time lower bounds for strong inapproximability of maximum k -coverage, unique set cover and related problems (via t -wise agreement testing theorem)

    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 Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 , pages 62--81. SIAM , 2020

    2020

  48. [50]

    Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back

    Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back. Theor. Comput. Sci. , 1028:115033, 2025

    2025

  49. [51]

    Parameterized complexity and approximation algorithms

    D \' a niel Marx. Parameterized complexity and approximation algorithms. Comput. J. , 51(1):60--78, 2008

    2008

  50. [52]

    Cutting hyperplane arrangements

    Jir \' Matousek. Cutting hyperplane arrangements. In Raimund Seidel, editor, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990 , pages 1--9. ACM , 1990

    1990

  51. [53]

    Nemhauser, Laurence A

    George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I . Math. Program. , 14(1):265--294, 1978

    1978

  52. [54]

    Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond

    Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms , 9(1):11:1--11:23, 2012

    2012

  53. [55]

    On MAX-SAT with cardinality constraint

    Fahad Panolan and Hannane Yaghoubizade. On MAX-SAT with cardinality constraint. Theor. Comput. Sci. , 1025:114971, 2025

    2025

  54. [56]

    Approximating csps with global cardinality constraints using SDP hierarchies

    Prasad Raghavendra and Ning Tan. Approximating csps with global cardinality constraints using SDP hierarchies. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 373--387. SIAM , 2012

    2012

  55. [57]

    On the density of families of sets

    Norbert Sauer. On the density of families of sets. J. Comb. Theory A , 13(1):145--147, 1972

    1972

  56. [58]

    Combinatorial optimization: polyhedra and efficiency , volume 24

    Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency , volume 24. Springer Science & Business Media, 2003

    2003

  57. [59]

    Parameterized matroid-constrained maximum coverage

    Fran c ois Sellier. Parameterized matroid-constrained maximum coverage. In Inge Li G rtz, Martin Farach - Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands , volume 274 of LIPIcs , pages 94:1--94:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Inf...

    2023

  58. [60]

    Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time

    Piotr Skowron and Piotr Faliszewski. Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. J. Artif. Intell. Res. , 60:687--716, 2017

    2017

  59. [61]

    A combinatorial problem; stability and order for models and theories in infinitary languages

    Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics , 41(1):247--261, 1972

    1972

  60. [62]

    Improved performance of the greedy algorithm for partial cover

    Petr Slav \' k. Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. , 64(5):251--254, 1997

    1997

  61. [63]

    Best possible approximation algorithm for MAX SAT with cardinality constraint

    Maxim Sviridenko. Best possible approximation algorithm for MAX SAT with cardinality constraint. Algorithmica , 30(3):398--405, 2001

    2001

  62. [64]

    FPT algorithms for domination in sparse graphs and beyond

    Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in sparse graphs and beyond. Theor. Comput. Sci. , 770:62--68, 2019

    2019

  63. [65]

    Vazirani

    Vijay V. Vazirani. Approximation algorithms . Springer, 2001

    2001

  64. [66]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264--280, 1971

    1971

  65. [67]

    Laurence A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Comb. , 2(4):385--393, 1982

    1982

  66. [68]

    Hochbaum , title =

    Dorit S. Hochbaum , title =. 1997 , url =. doi:10.1145/261342.571216 , timestamp =

    work page arXiv 1997

  67. [69]

    V. S. Anil Kumar and Sunil Arya and H. Ramesh , editor =. Hardness of Set Cover with Intersection 1 , booktitle =. 2000 , url =. doi:10.1007/3-540-45022-X\_53 , timestamp =

    doi:10.1007/3-540-45022-x 2000

  68. [70]

    Wolsey , title =

    Laurence A. Wolsey , title =. Comb. , volume =. 1982 , url =. doi:10.1007/BF02579435 , timestamp =

    work page doi:10.1007/bf02579435 1982

  69. [71]

    Improved Performance of the Greedy Algorithm for Partial Cover , journal =

    Petr Slav. Improved Performance of the Greedy Algorithm for Partial Cover , journal =. 1997 , url =. doi:10.1016/S0020-0190(97)00182-8 , timestamp =

    work page doi:10.1016/s0020-0190(97)00182-8 1997

  70. [72]

    2018 , url =

    Daniel Lokshtanov and Pranabendu Misra and Fahad Panolan and Saket Saurabh , title =. 2018 , url =. doi:10.1145/3170444 , timestamp =

    doi:10.1145/3170444 2018

  71. [73]

    CoRR , volume =

    Irit Dinur and David Steurer , title =. CoRR , volume =. 2013 , url =. 1305.1979 , timestamp =

    Pith/arXiv arXiv 2013

  72. [74]

    50th Annual

    Nikhil Bansal and Subhash Khot , title =. 50th Annual. 2009 , url =. doi:10.1109/FOCS.2009.23 , timestamp =

    doi:10.1109/focs.2009.23 2009

  73. [75]

    Subhash Khot and Oded Regev , title =. J. Comput. Syst. Sci. , volume =. 2008 , url =. doi:10.1016/J.JCSS.2007.06.019 , timestamp =

    work page doi:10.1016/j.jcss.2007.06.019 2008

  74. [76]

    A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem , booktitle =

    Reuven Bar. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem , booktitle =. 1983 , timestamp =

    1983

  75. [77]

    Hochbaum , title =

    Dorit S. Hochbaum , title =. 1982 , url =. doi:10.1137/0211045 , timestamp =

    doi:10.1137/0211045 1982

  76. [78]

    A parameterized view on matroid optimization problems , journal =

    D. A parameterized view on matroid optimization problems , journal =. 2009 , url =. doi:10.1016/J.TCS.2009.07.027 , timestamp =

    work page doi:10.1016/j.tcs.2009.07.027 2009

  77. [79]

    Hitting Set for Hypergraphs of Low VC-dimension , booktitle =

    Karl Bringmann and L. Hitting Set for Hypergraphs of Low VC-dimension , booktitle =. 2016 , url =. doi:10.4230/LIPICS.ESA.2016.23 , timestamp =

    work page doi:10.4230/lipics.esa.2016.23 2016

  78. [80]

    Approximating low-dimensional coverage problems , booktitle =

    Ashwinkumar Badanidiyuru and Robert Kleinberg and Hooyeon Lee , editor =. Approximating low-dimensional coverage problems , booktitle =. 2012 , url =. doi:10.1145/2261250.2261274 , timestamp =

    work page arXiv 2012

  79. [81]

    Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,

    Sushmita Gupta and Pallavi Jain and Souvik Saha and Saket Saurabh and Anannya Upasana , title =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,. 2025 , url =. doi:10.24963/IJCAI.2025/433 , timestamp =

    work page doi:10.24963/ijcai.2025/433 2025

  80. [82]

    Fomin, F. V. and Lokshtanov, D. and Saurabh, S. , booktitle =. Efficient computation of representative sets with applications in parameterized and exact algorithms , year =

Showing first 80 references.

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.