PaperlayerView exact revision on arXiv

Source-linked AI summary

A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

Yu Liu

arXiv:2609.03685v2cs.DScs.CC

TL;DR

The paper asks how to select a feasible set non-adaptively to maximize expected Top-k sum when the realized values are independent and nonnegative. It approximates truncated occupancy with signatures that can be realized by packing or covering LPs, or by query-weight exact-sum. This yields PTAS guarantees across those families, with matching limits on generic faster schemes for the stated classes.

  • Problem

    For general feasible families, prior k = 1 methods and cardinality-bound Top-k results do not provide a PTAS for non-adaptive expected Top-k sum at arbitrary k.

    Source: §1 · p. 2

  • Method

    The algorithm approximates p → E[min(k,N(p))] with occupancy or mixture-quantile signatures and realizes them through fixed-dimensional LPs or query-weight exact-sum.

    Source: §1 · p. 2

  • Results

    Every fixed-d packing family has a PTAS for every k, while no generic FPTAS exists unless P = NP and no generic EPTAS exists unless W[1] = FPT.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The signatures also yield PTASes for query-weight exact-sum families and for minimizing expected Top-k sum on fixed-d covering families.

    Source: §15 · pp. 16–17

    The packing lower bounds rule out uniformly faster schemes across the whole class, but do not classify which concrete families necessarily lack a constant-factor algorithm or PTAS.

    Source: §4 · p. 9

Abstract

from arXiv · show

We study non-adaptive selection of a feasible set $S$ that maximizes the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises in team hiring and as VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative packing family, whose natural LP has $d=O(1)$ packing inequalities with binary coefficients. We give a PTAS for every $k\ge 1$ on every such family, including binary one- and two-dimensional knapsack, by approximating the occupancy functional $p\mapsto\mathbb{E}[\min(k,N(p))]$ and realizing the resulting signatures in the packing LP. As a generic guarantee the scheme is essentially optimal: there is no FPTAS that works for every such $\mathcal{F}$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$. An incomparable sufficient condition is a query-weight exact-sum oracle (DAG paths, matchings), which likewise yields a PTAS for every $k$. The same signatures give a PTAS for $\min_{S\in\mathcal{F}}\mathbb{E}[\mathrm{Top}_k(S)]$ on every fixed-$d$ covering family; two-dimensional covering knapsack rules out a generic FPTAS on that class.

1 Introduction

The paper studies non-adaptive selection maximizing the expected sum of the k largest realized values, where prior maximum and Top-k results do not provide a general-family decoder. It introduces occupancy-based signatures and realization methods that yield approximation guarantees across packing, covering, and query-weight exact-sum families.

2 Related work

  • Prior Top-k extensions were tied to cardinality or probe-budget constraints, and k = 1 methods do not extend directly because a void probability does not control truncated occupancy.The adaptive constant-k PTAS also does not provide a decoder for general packing or covering families or growing k in the non-adaptive model.Source: §1 · p. 2, §2 · pp. 3–4

3 Technical overview

  • The core sketches approximate p → E[min(k,N(p))] using occupancy histograms for smaller k and a mixture-quantile type for larger k.The ranges meet at k = Θ(1/ε^2); either signature can be realized through exact-sum or fixed-dimensional packing and covering LPs.Source: §1 · p. 2, §3 · pp. 4, 6

1 Introduction

  • Every fixed-d packing family admits a PTAS for expected Top-k sum for every k, while no generic FPTAS exists unless P = NP and no generic EPTAS exists unless W[1] = FPT.Two-dimensional knapsack witnesses the lower bounds, making the generic packing PTAS essentially optimal.Source: §1 · pp. 2–3
  • Query-weight exact-sum is an incomparable sufficient condition for a PTAS, covering families such as DAG paths and matchings that are not fixed-d packing.Binary knapsack is packing but lacks this condition unless capacities are encoded in unary; cardinality and unary knapsack lie at the intersection.Source: §1 · pp. 2–3
  • The same signatures yield a PTAS for minimizing expected Top-k sum on every fixed-d covering family, while two-dimensional covering knapsack rules out a generic FPTAS.A query-weight exact-sum condition also yields a PTAS for minimization.Source: §1 · pp. 2–3

3 Technical overview

  • A surplus scale W = kT brackets OPT between W and 2W, and a mean-preserving fold retains large-atom lotteries that naive truncation can destroy.A grid then discretizes the folded distributions for the occupancy sketches.Source: §3 · p. 5
  • For occupancy sketches, the signature captures truncated occupancy rather than only the void probability used for expected maxima.Large coordinates are histogrammed on unsaturated layers, while tiny probabilities are replaced by a Poisson variable with matching total mass.Source: §3 · p. 5
  • Sparse lotteries transfer max-sum hardness to expected Top-k, and exact-sum or packing LPs realize signatures without changing the stochastic analysis.The hardness encoding already works at k = 1.Source: §3 · pp. 5–6

4 Model and main theorems

The model selects a feasible set before observing independent nonnegative discrete values, seeking to maximize or minimize the expected sum of the k largest. The main theorems establish PTAS guarantees on fixed-dimensional packing and covering families and on families with query-weight exact-sum, alongside uniform lower bounds.

4 Model and main theorems

  • The maximization input comprises independent nonnegative discrete laws, a feasible family, k, and ε; the output seeks expected value at least (1−O(ε))OPT.For minimization, the target is at most (1+O(ε))OPTmin.Source: §4 · p. 6
  • For fixed d, every d-dimensional packing family admits a PTAS for maximizing expected Top-k sum for every k ≥ 1.The running time is n^f(d,1/ε), with f independent of n; the construction uses occupancy or quantile signatures realized through the packing LP.Source: §4 · p. 7
  • For every fixed-d covering family, minimizing expected Top-k sum admits a PTAS for every k.The covering realization uses the same signatures in a covering LP, raising at most O(d) fractional variables to 1; downward-closed packing is excluded because its minimum is the empty set.Source: §4 · p. 8
  • Query-weight exact-sum yields a PTAS for maximization for every k, using occupancy and quantile schemes across complementary k ranges.The same exact-sum condition yields a minimization PTAS with the same time bounds.Source: §4 · p. 8
  • No single FPTAS or EPTAS works on every fixed-d packing family unless P = NP or W[1] = FPT, respectively.Two-dimensional knapsack supplies the witness; these are uniform lower bounds, not a classification of every concrete family.Source: §4 · p. 9
  • The negative results are uniform, and identifying which concrete families necessarily lack a constant-factor algorithm or PTAS remains open.Two-dimensional covering knapsack rules out a generic FPTAS on fixed-d covering families.Source: §4 · p. 9

5 Preliminaries

The preliminaries connect expected Top-k value to Poisson-binomial occupancy, then use surplus searches to transfer sum-optimization guarantees to stochastic Top-k optimization. For minimization, fixed-dimensional covering families and query-weight exact-sum families provide the required min-sum guarantees.

5 Preliminaries

  • A Poisson-binomial occupancy count N with mean µ satisfies E[min(k,N)] ≥ kµ/(k+µ), and its functional is nondecreasing, concave, and ℓ1-Lipschitz.When µ ≥ 2k + C0 log(k/ε), the functional is within ε² of k; Le Cam approximation and Poisson mean stability also support comparisons.Source: §5 · p. 9

6 Surplus Constant Approximation

  • For k=1, earlier algorithms preserve a void probability or a truncated-mean scale, while arbitrary k requires controlling the full occupancy functional.The surplus fixed point has a root because the maximum achievable surplus is continuous and nonincreasing in T, while kT increases.Source: §6 · pp. 9–10
  • For independent nonnegative values, Top-k is bounded above by kT plus total truncated surplus, and surplus at least kT implies expected Top-k at least kT.At a surplus fixed point, the selected set is a 2-approximation; for k=1 this recovers Liu's truncation sandwich.Source: §6 · p. 10
  • A decreasing surplus search transfers an α-approximate max-sum oracle into a k-independent approximation guarantee for every k; query-weight exact-sum also yields a max-sum FPTAS.For α=1, the ratio is 1/(2(1+ε)); cuts can use the Goemans–Williamson oracle with α≈0.878.Source: §6 · p. 10
  • Fixed-dimensional covering families have deterministic min-sum PTASes, so the min-sum transfer gives a Top-k minimization PTAS for every k.Query-weight exact-sum families also obtain a suitable scale for the decoder; downward-closed families have the trivial empty-set minimum, so covering-type families are the interesting case.Source: §6 · pp. 10–11

7 Reducing the support

The support-reduction step folds large tails into bounded distributions while preserving their contribution, then grids the support with controlled loss. A fold-back bound transfers guarantees on the folded variables to the original objective.

7 Reducing the support

  • Capping large atoms can destroy objective value: a lottery with mean Θ(W) may fall to Θ(εW) after truncation at M=W/ε.The method therefore folds the tail rather than deleting it.Source: §7 · p. 11
  • The mean-preserving fold produces variables supported on [0,M], with occupancy above M removed and occupancy below M stochastically dominating the original.The fold adds tail mass below M when the survival-function minimum does not bind.Source: §7 · p. 11
  • For inputs Xi with supp(Xi) ⊆ [0,M], rounding each to δ⌊Xi/δ⌋ at δ=εW yields h=1/ε² support values and pathwise loss 0 ≤ Topk(X)−Topk(˜X) < kεW.Source: §7 · p. 11
  • After accuracy rescaling, the fold-and-grid error is O(ε) relative to OPT, and fold-back incurs at most a factor 1+5ε when the folded value is at most (1+4ε)W.The stated pre-rescaling relative error is O((c²+k)ε).Source: §7 · p. 11

8 Type-histogram signatures

Type-histogram signatures approximate the occupancy functional with additive, realizable summaries for gridded variables. For large k, a mixture-quantile proxy and multiplicative rounding avoid the small-k scheme's dependence on many occupancy layers.

8 Type-histogram signatures

  • An additive signature records tiny-probability mass and counts of binned larger probabilities across layers, then evaluates an independent-sum proxy, saturating layers whose proxy mean reaches Λ.The signature's mixed-radix encoding has magnitude n^O(h)(kΛ/ε)^O(hB), with hB=O(kΛ²/ε⁶).Source: §8 · p. 12
  • For an unsaturated layer, the true occupancy functional and signature proxy differ by at most 4ε²; saturated layers are within O(ε²) of k and of one another.Equal signatures make both sets' values O(ε)W-close to the same proxy.Source: §8 · p. 12
  • The small-k signature scheme quantizes tiny mass to prevent accumulated error, but its n-exponent depends on k, so it is not an EPTAS even for fixed k.The uniform-grid occupancy scheme has n-exponent O(k²/ε²) after accuracy substitution, plus a k-dependent histogram factor.Source: §8 · p. 12, §9 · p. 12

9 A quantile scheme for large k

  • A mixture quantile brackets the k-th occupancy using strict and weak exceedance counts; when the selected set has at most k items, Top-k equals their total value pathwise.Candidate quantiles are input atoms or grid heights after multiplicative rounding.Source: §9 · p. 13
  • When k is at least C/ε², the quantile proxy's expected value differs from Top-k by O(ε) relatively, and decoding matches residual types at a mixture quantile.The proxy error is O(k^-1/2) before the large-k threshold and supports a window around occupancy k.Source: §9 · p. 13
  • Multiplicative rounding supports each variable on a grid of size O(ε^-1 log(n/ε)) while preserving Top-k within multiplicative O(ε) and additive O(ε)W pathwise.Uniform rounding would reintroduce a factor k in relative error.Source: §9 · p. 13

10 Packing PTAS via the natural LP

The packing PTAS realizes occupancy signatures in the natural LP, adapting its construction to small and large k while retaining unrounded capacities. The same decoder yields a covering PTAS by raising fractional variables, but requires fixed-dimensional covering structure.

10 Packing PTAS via the natural LP

  • The packing construction derives W from a max-sum packing PTAS, with W≤OPT≤5W, and uses internal accuracy scaled to the requested accuracy.Capacities are never rounded, and the LP realizes the decoder's approximate signatures.Source: §10 · p. 14
  • For large k, the LP uses a three-coordinate type and surplus-heavy enumeration; dropping at most d+6 fractional items changes occupancy by O(1) and surplus by O(ε)W.Since k=Ω(1/ε²), the occupancy loss is a relative O(ε).Source: §10 · p. 14
  • For small k, many histogram coordinates can leave too many fractional items, so the method enumerates heavy items and uses tiny residual probabilities plus Poissonization to control signature error.The LP has packing inequalities, slabs for non-raised layers, and covering inequalities for raised layers; dropping its fractionals changes each residual mean by at most ε²/2.Source: §10 · p. 14
  • The packing scheme is a PTAS whose n-exponent may depend on d and 1/ε; the paper rules out a generic EPTAS or FPTAS for this class.The covering LP analog raises at most d+2D+C fractional variables to 1, preserving covering while changing each signature within the drop budget.Source: §10 · p. 14, §11 · p. 14

11 Covering PTAS via the natural LP

  • For covering, the decoder's folded value is at most (1+4ε)W, and fold-back bounds the original objective; a constant min-sum approximation on an arbitrary up-set is insufficient.Vertex cover has a 2-approximation for min-sum but dimension d=Θ(m), outside the fixed-dimensional setting.Source: §11 · p. 15

12 Exact-Sum Realization

Exact-sum realization gives another PTAS route, incomparable with fixed-dimensional packing, while two-dimensional knapsack rules out generic FPTAS and EPTAS guarantees for packing. The conclusion extends the signature-based approach to covering and leaves adaptive PTAS questions open.

12 Exact-Sum Realization

  • Exact-sum returns a set matching a folded optimum’s occupancy signature, and the true objective and proxy Val are interchangeable after realization.Mixed-radix signature counting contributes an n^O(1/ε²) factor.Source: §12 · p. 15

13 No generic EPTAS or FPTAS on packing

  • For max over S in F of E[Top_k(S)], unless P = NP no FPTAS exists, and unless W[1] = FPT no EPTAS exists, already for k = 1.The proof uses a lottery encoding; cardinality for k = 1 already admits an EPTAS [2].Source: §13 · p. 16

14 Instantiations

  • Packing and exact-sum PTAS guarantees are incomparable: binary knapsack lies only on the packing side, while DAG paths lie only on the exact-sum side.Cuts lie only on the first, max-sum transfer rung; both PTAS columns apply to cardinality.Source: §14 · p. 16

15 Conclusion and Open Problems

  • The two occupancy sketches replace the k = 1 void-probability signature while retaining the packing and exact-sum realization primitives.A PTAS follows for every k on fixed-dimensional packing; two-dimensional knapsack makes the generic PTAS essentially optimal in that class.Source: §15 · pp. 16–17
  • The covering counterpart realizes the same signatures by raising fractionals in the covering LP, yielding a PTAS for every k on fixed-dimensional covering families.A min-sum constant on an arbitrary up-set does not suffice; vertex cover is the covering analogue of the cut witness.Source: §15 · p. 17
  • Whether adaptive PTASs exist for general fixed-dimensional packing or covering families remains open; per-instance boundaries for uniform hardness also remain questions.The paper also asks which exact-sum families outside packing and covering admit EPTASs or FPTASs.Source: §15 · p. 17

A Proofs for Section 5

These proofs express Top-k through thresholded occupancy, establish approximation properties of the occupancy functional, and analyze surplus-threshold searches. The bounds support constant-factor guarantees for the maximization and minimization settings.

A Proofs for Section 5

  • Top-k admits a layer-cake representation whose threshold integrand is the minimum of k and the number of coordinates above threshold.On a δ-grid, counting coordinates at least rδ changes Top-k by at most kδ.Source: A Proofs for Section 5 · p. 20
  • For Bernoulli occupancy, adding an item of probability p increases expected truncated count by p times the probability the prior count is below k.This yields the lower bound E[min(k,N)] ≥ kμ/(k+μ).Source: A Proofs for Section 5 · p. 20
  • The occupancy functional is nondecreasing, coordinatewise concave, 1-Lipschitz in the probability vector, and bounded by min(k,Σp_i).When μ is sufficiently above k, its value is within ε² of k; Poisson approximation incurs a total-variation error controlled by k.Source: A Proofs for Section 5 · p. 20
  • Coupling Poisson processes shows that increasing intensity changes expected truncated occupancy by at most one per unit intensity.The proof bounds the increment by the chance of adding a point, which is dλ.Source: A Proofs for Section 5 · p. 20

B Proofs for Section 6

  • Truncating each value at T bounds Top-k between the larger of kT and total surplus, and kT plus total surplus.This links the threshold search’s surplus objective to the original Top-k objective.Source: B Proofs for Section 6 · p. 20
  • The threshold integral comparisons use the nonincreasing expected count above t to relate Top-k to the truncated-mean scale.The proof applies this comparison to obtain the lower bound used in the min-sum guarantee.Source: B Proofs for Section 6 · pp. 20–21
  • The decreasing surplus search for maximization returns a set with expected Top-k at least kT₀ when it halts at threshold T₀.Its geometric threshold sequence takes O(ε^-1 log(range)) iterations.Source: B Proofs for Section 6 · p. 21
  • At halt T0, the output has upper bound (1+α)kT0, while OPTmin is at least kT0/(1+ε), yielding ratio (1+α)(1+ε) for minimizing expected Top-k.Source: B Proofs for Section 6 · p. 21

C Proof of Proposition 4.7

The proof rounds weights so exact-sum queries can find an approximate max-sum solution, then uses occupancy bounds and folded signatures to transfer guarantees to Top-k objectives. It also establishes the corresponding min-sum and min-Top-k guarantees for query-weight families.

C Proof of Proposition 4.7

  • Weight rounding lets exact-sum queries produce a max-sum FPTAS without enumerating targets at the original weights’ potentially exponential scale.The rounded target search uses polynomially many oracle calls and runs in time polynomial in the family encoding, n, and 1/ε.Source: C Proof of Proposition 4.7 · pp. 21–22
  • Scanning feasible rounded targets from smallest to largest gives a min-sum FPTAS, so the query-weight-family result applies to minimization as well.The passage states that Theorem 6.7 then applies on every query-weight family.Source: C Proof of Proposition 4.7 · p. 22

D Proofs for Section 7

  • For the folded occupancy tails, the total tail mass is bounded by 2cW and each normalized item tail by 2cε.These bounds follow from the cited lemma when cε ≤ 1/4.Source: D Proofs for Section 7 · p. 22
  • Capping tails at M controls the original expected Top-k by U/(1−4ε), where U is the folded expectation.The proof bounds the mass lost to the cap before applying this comparison.Source: D Proofs for Section 7 · p. 23
  • For min-Top-k, the algorithm folds and grids at an estimated scale, matches signatures, and returns the set with smallest folded expectation.The resulting folded value is bounded by (1+4ε)W for ε ≤ 1/20, enabling the cited transfer bound.Source: D Proofs for Section 7 · p. 23

E Proofs for Section 8

The Section 8 proof bounds the errors from quantizing tiny mass, replacing bucket representatives, and matching proxy signatures across layers. The appendix also establishes monotone submodularity of expected Top-k and recalls the associated greedy approximation baseline.

E Proofs for Section 8

  • Quantization and proxy replacements contribute errors totaling at most 4ε² for the resulting occupancy law.The proof separately bounds tiny-item removal, tiny-mass adjustment, bucket replacement, and the remaining proxy error.Source: E Proofs for Section 8 · pp. 23–24
  • Sets sharing layer signatures have an O(ε)W proxy gap after summing over layers, with no additional factor of k.The proof uses the shared saturation bit and signature at each layer.Source: E Proofs for Section 8 · p. 24

F Monotone submodularity

  • Expected Top-k is nonnegative, monotone, and submodular; cardinality greedy achieves 1−1/e, a baseline that is not a PTAS.The continuous greedy algorithm extends the same ratio to matroids.Source: F Monotone submodularity · p. 24

G Proofs for Section 9

The Section 9 proofs relate Top-k to thresholded occupancy and surplus, then use these quantities to approximate the objective. The packing realization proof matches signatures through residual LPs and handles large- and small-k cases separately.

G Proofs for Section 9

  • For a threshold T with occupancy means bracketing k, the proof bounds the gap between a threshold-based estimator and Top-k using shortage and overflow terms.Independent Bernoulli threshold indicators and thinning bound the shortage; the overflow is controlled using the truncated excess values.Source: G Proofs for Section 9 · pp. 24–25
  • Zeroing atoms below τ loses less than kτ, while multiplicative rounding of surviving values preserves Top-k within a factor of 1+ε.The surviving rounded values lie on a grid over [τ,W/ε].Source: G Proofs for Section 9 · p. 25

H Packing LP realization

  • A packing LP basic feasible solution has at most d+2D+C fractional coordinates, and zeroing them preserves packing feasibility.The dropped coordinates can reduce signature coordinates, with the displayed lower bound recording the worst-case loss.Source: H Packing LP realization · pp. 25–26
  • In the large-k packing case, enumerating surplus-heavy items and realizing a residual LP yields an O(εout)OPT guarantee.The proof drops only O(1) fractional items and controls the resulting occupancy and surplus changes.Source: H Packing LP realization · p. 27
  • For small k, the proof guesses saturated layers and LP-heavy items, matches tiny-mass signatures, and obtains O(εout)OPT error after accuracy substitution.The running-time exponent depends on d and 1/εout.Source: H Packing LP realization · pp. 27–28

I Covering LP realization

The covering proof enumerates guesses and realizes integral coverings through residual LPs, treating large and small k separately. After the folded-value transfer, the returned set approximates the minimum expected Top-k.

I Covering LP realization

  • For large k, the proof enumerates surplus-heavy items and residual targets, then raises at most d+6 fractional coordinates to realize an integral covering.The resulting occupancy slack is O(1), and the surplus increase is O(ε)W.Source: I Covering LP realization · p. 28
  • For small k, the proof guesses saturated layers and LP-heavy items, matches tiny-mass slabs, and uses occupancy robustness before substituting the requested accuracy.The resulting error is O(εout)OPTmin and the n-exponent is f(d,1/εout).Source: I Covering LP realization · p. 28
  • The returned covering set satisfies E[Topk(S;X)] ≤ (1+O(ε))OPTmin.The proof obtains this guarantee by transferring the returned set’s folded value to the original laws.Source: I Covering LP realization · p. 28

J Proofs for Section 12

The proofs bound the signatures used by exact-sum enumeration and establish approximation guarantees for both occupancy sketches. They also derive the running-time bounds and handle the large-set case through a mixture quantile.

Proofs for Section 12

  • Theorem 4.12 selects a set with the optimal set’s signature using exact-sum, then applies Theorems 7.6 and 8.4 with c = 2.The enumeration finds a set with the same signature whenever the optimal set is feasible.Source: J Proofs for Section 12 · p. 28
  • After substituting ε ← ε/(C(k + 1)), Corollary 4.13 has an n-exponent of O(k²/ε²), or O(1/ε⁶) when k ≤ C/ε².The substitution gives h = Θ(k²/ε²) and hB = O(k⁷Λ′²/ε⁶).Source: J Proofs for Section 12 · p. 29
  • For Theorem 4.14, folding and multiplicative rounding each change the objective by O(ε)-scale error; matching a quantized triple at a mixture quantile then supports the large-set guarantee.When the optimum has at most k items, the triple at T = 0 determines its size and yields the corresponding guarantee; otherwise the mixture-quantile argument applies.Source: J Proofs for Section 12 · p. 29
  • The occupancy signature uses h = 1/ε² layers and at most 2kΛ²/ε⁴ histogram buckets per layer; mixed-radix encoding yields the stated enumeration size.Unsaturated layers have at most kΛ²/ε² big items, while saturated layers store one bit.Source: J Proofs for Section 12 · p. 29

K Hardness reductions

The reductions transfer deterministic max-sum hardness to stochastic maximum value using sparse Bernoulli lotteries, and use two-dimensional knapsack constructions to rule out generic approximation schemes for packing and covering.

Sparse lotteries

  • For independent Xi=B(wi,q), with wi≥0 and q∈(0,1), q(1−q)^(n−1)w(S) ≤ E[max(S)] ≤ qw(S); if E[max(S)] ≥ ρ OPTE, then w(S) ≥ ρ(1−q)^(n−1)OPTw.Source: K Hardness reductions · p. 30

Hardness reductions

  • Independent-set hardness rules out a constant-factor algorithm for E[max] on every membership family, already at k = 1.The reduction would give a (ρ/2)-approximation for independent set, a contradiction.Source: K Hardness reductions · p. 30
  • Max-cut APX-hardness rules out a PTAS for E[max] on every cut family, despite a constant-factor algorithm for that family.The sparse lotteries are essential: deterministic edge weights would encode the heaviest cut edge, not cut weight.Source: K Hardness reductions · pp. 30–31
  • A generic packing-class FPTAS would yield an FPTAS for two-dimensional knapsack, while an EPTAS would yield an EPTAS there, contradicting its known hardness.The two-dimensional knapsack family has d = 2, and the reduction’s firing probability depends on ε.Source: K Hardness reductions · p. 31
  • A Subset Sum instance is feasible in some constructed two-dimensional covering instance exactly when a subset sums to the target; this rules out an FPTAS unless P = NP.The construction uses unit costs, and an FPTAS would decide the instances exactly.Source: K Hardness reductions · pp. 31–32
Loading 2609.03685v2…