Pith. sign in

REVIEW 2 major objections 5 minor 61 references

A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper gives the first polynomial-time approximation algorithms for generating diverse collections of solutions to NP-hard problems, using a framework that turns dynamic programs plus a k-best enumeration routine into diversity…

desk verdict A promising framework and a genuinely new planar MWIS/MWVC result, but the advertised diverse-knapsack PTAS is broken by a wrong denominator in Lemma 18's weight scaling. read the letter →

arxiv 2501.12261 v4 pith:C5PBQQCN submitted 2025-01-21 cs.CG cs.DS

Waldo Gálvez , Mayank Goswami , Arturo Merino , GiBeom Park , Meng-Tsung Tsai , Victor Verdugo This is my paper · ORCID
classification cs.CGcs.DS MSC 68W25
keywords diversesolutionsNP-hardproblemsapproximationalgorithmsresourceaugmentationknapsackplanargraphsk-bestenumerationlocalsearch
verification ladder T0 review T1 audit T2 compute T3 formal

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 claims to close a gap: for NP-hard problems, the only previously known algorithms for producing k diverse feasible solutions were FPT with exponential dependence on the input size, while polynomial-time approximations existed only for problems in P. Its framework, stated as Theorem 9, shows that if a problem supplies a resource-augmented solution space, a diversity-preserving collection inside it, a budget-constrained k-best enumeration routine, and an exact optimizer for small k, then one obtains a (1-epsilon)-approximation to the sum of pairwise symmetric differences with only a (1-delta)c quality relaxation. Applying the framework yields a PTAS for diverse knapsack with small capacity violation, and (1-epsilon)-approximations for diverse planar maximum-weight independent sets and minimum-weight vertex covers in $2^{{O(k/(delta epsilon^2))}}$ $n^{{O(1/epsilon)}}$ time. The practical value is that near-optimal, genuinely different alternatives can be generated efficiently, which matters for decision support, robustness, and energy efficiency in applications such as sensor networks.

What carries the argument

The load-bearing object is the budget-constrained k-best enumeration (k-BCBE) problem: given an extra integer-valued score r on subsets, return the k distinct c-optimal solutions with the largest r-values. Theorem 9 combines a k-BCBE oracle with the MAX-SUM local-search algorithm of [12], which reaches diversity at least max{1/2, 1 - 2/(k+1)} of optimum after O(k log k) swaps, and with the enumeration-to-swap translation of [27]. Conditions (1) and (2) supply the resource-augmented space F'_c (solutions that are only (1-delta)c-optimal, for example planar independent sets avoiding a deleted marginal layer) and the guarantee that moving from F_c to F'_c costs at most epsilon/2 in diversity. The k-BCBE routines are built by adding a score dimension to textbook dynamic programs and applying the k-best method of [38].

What would settle it

Take a knapsack instance with capacity 100, item A of weight 1 and profit 100, and item B of weight 100 and profit 60, with c = 0.5 and delta = gamma = 0.1. Both {A} and {B} are c-optimal, but the weight scaling of Lemma 18 maps B's weight to roughly 2000 while the scaled bound is 22, so B leaves the search space; an implementation that then outputs only solutions derived from A contradicts the claimed (1-epsilon) diversity guarantee over the c-optimal space. Checking whether the algorithm's output diversity exceeds what is achievable using only sets of weight near 1 would settle the matter.

Watch

Extended reading notes

Core claim

The central discovery is that the obstacle to polynomial-time diverse solutions for NP-hard problems is not diversity itself but the need to search the full space of c-optimal solutions. The paper defines a resource-augmented search space F'_c of solutions that are only (1-delta)c-optimal and shows that if F'_c contains a collection whose pairwise sum is within (1-epsilon/2) of the optimum over F_c, then applying the local-search/k-best enumeration framework inside F'_c loses only a (1-epsilon) factor in diversity while degrading quality by only delta. This reduces the design task to two ingredients: a budget-constrained k-best enumeration routine over F'_c and an exact diverse optimizer for small k. For the paper's target problems, both ingredients come from augmenting known dynamic programs with an extra score dimension and using a k-best enumeration method; the planar applications additionally use a marginal-layer deletion argument to build F'_c.

Load-bearing premise

The scaling and rounding step assumes that one feasible solution S can be used to normalize item weights, which only works when S has weight comparable to the knapsack capacity; otherwise a feasible solution of weight near capacity can be rounded above the search bound and silently dropped, breaking both the diversity and capacity guarantees.

Editorial extensions

If this is right

  • Diverse knapsack admits a PTAS with (1-delta) quality relaxation and solutions of weight at most (1+gamma)W, so a small capacity violation is the price of polynomial running time.
  • Diverse planar maximum-weight independent sets and minimum-weight vertex covers admit (1-epsilon)-approximations in 2^{O(k/(delta epsilon^2))} n^{O(1/epsilon)} time, making them PTASs when k = O(log n).
  • Rectangle packing, enclosing polygons, and maximum-weight independent sets on unit-disk graphs of points in convex position inherit the framework with polynomial or f(k)poly(n) running times and explicit diversity-quality trade-offs.
  • The framework converts the design task for any NP-hard problem with a textbook dynamic program into two ingredient tasks, namely k-BCBE and an exact small-k optimizer, so the results are not isolated algorithms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • [Editorial inference] The resource-augmentation design pattern is transferable: any NP-hard problem with a PTAS that restricts to a structured subspace may be a candidate, provided the missing structure contributes only an epsilon fraction to diversity.
  • [Editorial inference] The k-BCBE ingredient suggests a generic recipe: take the existing dynamic program for the single-solution problem, add a dimension tracking the score function, and apply k-best enumeration; this could extend to other treewidth-bounded or geometric problems beyond those listed.
  • [Editorial inference] The guarantees concern average pairwise Hamming distance, not minimum pairwise distance; the paper itself connects max-min versions to Hamming-code computations, hinting that max-min diversity may be genuinely harder.
  • [Editorial inference] Because the local-search factor is max{1/2, 1 - 2/(k+1)}, a user with small k who wants strong diversity needs the exact small-k branch, which only applies when k < 4/epsilon; otherwise the guarantee may be closer to half the optimal diversity.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper proposes a general framework (Theorem 9) for computing k diverse, approximately optimal solutions to NP-hard optimization problems, building on the local-search approach of Cevallos et al. and the k-best enumeration ideas of Hanaka et al. and Gao et al. The framework requires four ingredients: a resource-augmented solution space F'_c with a diversity-preservation guarantee, a budget-constrained k-best enumeration (k-BCBE) algorithm, and an exact optimizer for small k. The authors apply the framework to diverse knapsack, diverse maximum-weight independent sets and minimum-weight vertex covers in planar graphs, rectangle packing, enclosing polygons, unit-disk graphs in convex position, and TSP tours, claiming the first poly(n,k) or f(k)poly(n)-time approximation algorithms for several of these problems. The appendices contain full proofs, including a marginal-strata lemma for planar graphs, a k-BCBE dynamic program on tree decompositions, and a scaling/rounding lemma for knapsack.

Significance. If the framework and its applications are correct, this is a substantial contribution: it would give the first polynomial- or f(k)poly(n)-time approximation algorithms for diverse-solution versions of several NP-hard problems, with the planar MWIS/MWVC result being particularly notable. The paper is also explicit about resource augmentation and about the trade-off between diversity and quality, and Theorem 15's k-BCBE on tree decompositions is a concrete algorithmic tool that may be reusable. The claims in the abstract are strong, and they are backed by detailed proofs rather than only sketches. However, the current text has load-bearing gaps in the knapsack scaling lemma and in the treatment of signed score functions inside the framework, so the significance is conditional on those being repaired.

major comments (2)
  1. [Appendix A, Lemma 18(1) and proof of Theorem 5(2)] The weight half of Lemma 18(1) is false as stated. The proof handles profits and says that the argument for weights is analogous, but the two arguments are not analogous: the profit scaling uses the c-optimality lower bound u(X) ≥ c·u(S) to absorb the floor losses, whereas for weights a feasible solution X is only known to satisfy w(X) ≤ W, and the reference weight w(S) can be arbitrarily small compared with W. Concretely, take n=2, W=100, item 1 with weight 1 and profit 1000, item 2 with weight 100 and profit 100, c=0.05, and S={item 1}. Then X={item 2} is c-optimal, but with γ=0.1 one has tilde W = floor((1.1/0.1)·2)=22 and tilde w(X) = floor(((22-2)/1)·100) = 2000 > 22 = tilde W, contradicting Lemma 18(1). Since Lemma 16 and the proof of Theorem 5(2) enumerate only the scaled space, such c-optimal solutions can be excluded, so the containment argument for the original optimal diverse collection breaks and the claimed (1-ε) diversity guarantee and (1+γ)W capacity guarantee are not established. The fix is to divide by W, or by a valid upper bound on all feasible weights, rather than by w(S), and to give an actual proof for the weight direction; the weighted planar extension at the end of Section 4 inherits the same defect because it reuses this 'analogous' scaling for vertex weights.
  2. [Section 3.1, Theorem 9 proof, and Condition (3)] Condition (3) of Theorem 9 is stated only for integer-valued score functions r with 0 ≤ r ≤ R, but Algorithm 1 defines r(e) = Σ_{S_j ∈ S−S_i} (1(e ∉ S_j) − 1(e ∈ S_j)), which can be negative. The proof of Theorem 9 then asserts that r(e) is the number of solutions containing e, but that is not what Equation (1) defines. This is not a cosmetic mismatch: the supplied k-BCBE algorithms are only written for nonnegative scores (Lemma 17 scans R' from nk down to 0, and Theorem 15's proof assumes 0 ≤ R' ≤ R). Adding a constant to every element score does not preserve the order of set scores when feasible solutions have different cardinalities, as they do for knapsack and for c-optimal independent sets. The framework should either extend Condition (3) to signed scores with a range of length 2nk and adapt the enumeration proofs, or explicitly define and justify a nonnegative score that exactly represents the best-swap objective.
minor comments (5)
  1. [Section 3.1, Algorithm 1] The summation in Equation (1) is written as Σ_{j∈[i]} but the intended range is j ∈ [k]; please correct the index range.
  2. [Lemma 11 proof] The phrase 'Let A_h be a bad set, every p in which satisfies (i′)' is not implied by the definition of a bad set; the counting argument should first assign each bad p to one of the k+1 witness types (one per h plus the diversity type) and then bound each type separately.
  3. [Theorem 15 proof] The bound 'the score of any subset of V is no greater than r(V)' is only valid for nonnegative scores; for the signed scores used in Algorithm 1 the correct bound is |r(S)| ≤ nk, so the proof should explicitly index scores in the range [−nk, nk].
  4. [Appendix E, proof of Theorem 28(1)] The definition w(e) = Σ_{h∈[k]}(1(e∉T_h) − 1(e∉T_h)) has the second indicator reversed; it should be 1(e∈T_h), otherwise the score is identically zero.
  5. [References] References [34] and [35] are the same paper and should be merged into a single entry to avoid duplication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the framework is conditional and the applications are derived from explicit DPs; the main risk is a non-circular correctness bug in Lemma 18's weight scaling.

full rationale

The claimed derivation chain is not circular. Theorem 9 is a conditional framework: it states that if a problem supplies a resource-augmented space F'_c, a near-optimal diverse collection inside it, a k-BCBE oracle, and an exact small-k optimizer, then a (1-epsilon)-APX with (1-delta)-RA follows. The proof supplies the local-search-to-enumeration argument from Cevallos et al. and Hanaka et al., which are external to the present author set, and it does not define OPTdiv(F_c) in terms of the output or of F'_c. The applications verify Conditions (1)-(2) by direct combinatorial arguments (marginal-strata Lemma 11, Proposition 12) and Conditions (3)-(4) by explicit DPs (Lemma 16, Theorem 15, Lemmas 17 and 18). The diverse-knapsack result is therefore a genuine derivation from stated assumptions. The one serious defect is Lemma 18's weight direction: it claims that w(X) <= W implies tilde-w(X) <= tilde-W when tilde-w_h divides by w(S), which is not true in general; this is a correctness bug in the proof of Theorem 5(2), not a circular reduction. No equation equates a prediction with a fitted input, and no load-bearing claim depends solely on a self-citation. The self-citations to [24] (Gao et al., with overlapping authors) are contextual: the paper uses [27] and [24] as design templates, but Theorem 9's proof and the application-specific DPs are spelled out in the text and checked against external textbook algorithms.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data. The approximation parameters epsilon, delta, gamma, and c are user inputs, and the scaling thresholds Utilde and Wtilde are derived. The axioms listed are the prior algorithmic results the paper imports. The invented-entities list is empty because F'_c, marginal strata, and container classes are mathematical constructions defined from the input, not new empirical entities.

assumptions (5)
  • standard math Local search analysis of Cevallos et al.: the swap heuristic for MAX-SUM diversification achieves max{1/2, 1-2/(k+1)} of optimal after O(k log k) swaps.
    Invoked in Section 3.1 as the core engine; not reproved here.
  • standard math Hanaka et al. technique: the best swapping solution can be found by querying the k+1 best solutions under a linear element score.
    Used in the proof of Theorem 9 to reduce local search to k-BCBE; the paper relies on this prior analysis.
  • standard math Baker's layered decomposition for planar graphs and the treewidth bound O(ell) for ell-outerplanar graphs.
    Foundation for the DMWIS-PG and DMWVC-PG application in Section 4; the paper adapts rather than re-proves Baker's PTAS.
  • ad hoc to paper The k-BCBE DP (Theorem 15) works for arbitrary integer score functions, including signed scores, with the same complexity.
    The paper states the DP for 0 <= r <= R but applies it to signed r(e); the shift to nonnegative scores is not specified and is not straightforward because it depends on set cardinality. This is an implicit assumption.
  • domain assumption Baste et al. exact FPT algorithm supplies Condition (4) for planar graphs in time 2^{O(ell k)} n^k.
    Used in Section 4.2 to bound f'(n,k); the exact diverse-solutions oracle is taken from prior work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems." pith.science (2026). https://pith.science/paper/C5PBQQCN

@misc{pith2026250112261,
  author       = {Pith},
  title        = {Pith review of: A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C5PBQQCN}},
  note         = {Machine review of arXiv:2501.12261}
}
abstract

There has been considerable recent interest in computing a diverse collection of solutions to a given optimization problem, both in the AI and theory communities. Given a classical optimization problem $\Pi$ (e.g., spanning tree, minimum cuts, maximum matching, minimum vertex cover) with input size $n$ and an integer $k\geq 1$, the goal is to generate a collection of $k$ maximally diverse solutions to $\Pi$. This diverse-X paradigm not only allows the user to generate very different solutions, but also helps make systems more secure and robust by handling uncertainty, and achieve energy efficiency. For problems $\Pi$ in P (such as spanning tree and minimum cut), there are efficient $\text{poly}(n,k)$ approximation algorithms available for the diverse variants [Hanaka et al. AAAI 2021, 2022, 2023, Gao et al. LATIN 2022, de Berg et al. ISAAC 2023]. In contrast, only FPT algorithms are known for NP-hard problems such as vertex covers and independent sets [Baste et al. IJCAI 2020, Eiben et al. SODA 2024, Misra et al. ISAAC 2024, Austrin et al. ICALP 2025], but in the worst case, these algorithms run in time $\exp((kn)^c)$ for some $c>0$. In this work, we address this gap and give $\text{poly}(n,k)$ or $f(k)\text{poly}(n)$ time approximation algorithms for diversification variants of several NP-hard problems such as knapsack, maximum weight independent sets (MWIS) and minimum vertex covers in planar graphs, geometric (rectangle) knapsack, enclosing points by polygon, and MWIS in unit-disk-graphs of points in convex position. Our results are achieved by developing a general framework and applying it to problems with textbook dynamic-programming algorithms to find one solution.

Figures

Figures reproduced from arXiv: 2501.12261 by the authors.

Figure 2
Figure 2. Illustration of decomposition of G. Here, G consists of 8 layers and ℓ = 2. The left one denotes a part of G with the level indicating to the left of each layer. The middle one is a collection of ℓ-outerplanar graphs constructed by removing L 0 3(G) from G. The right one is a collection of (ℓ + 2)-outerplanar graphs constructed by duplicating L 0 3(G). 1. Baker shows that there exists a MIS S ′ and a p ∈ {0, . . . ,… view at source ↗
Figure 4
Figure 4. Examples of a container-based solution (left), L&C-based solution (middle), and an L-packing of rectangles for two-dimensional geometric knapsack (right). Red lines show a guillotine cutting sequence for the solution, where numbers show the order of the cuts. We now present our results for the Diverse Rectangle Packing problem. Theorem 23 (Diverse Rectangle Packing). For Diverse Rectangle Packing, the following hold… view at source ↗
Figure 5
Figure 5. An illustration of an enclosing polygon Proof. We prove that there is a O(δ −1n 5k 2 )-time algorithm for the BCBE problem in the space F ′ (1−δ)c . By Corollary 10, then the result follows. First, by following the scaling and rounding scheme of [32] one can find a (1 − δ)-optimal solution by using the algorithm in [2]. Call it S. Now, according to Lemma 18, scale and round the value vi of each point to v˜ = j V˜ +n… view at source ↗
Figures from the paper (1 more)
Figure 6
Figure 6. Figure 6: An (n + 2)-vertex directed graph G = ([n] ∪ {s, t}, E) in which each minimum st-cut contains exactly n edges. 33 [PITH_FULL_IMAGE:figures/full_fig_p033_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 56 canonical work pages

  1. [1]

    Improved approximation algorithms and lower bounds for search-diversification problems

    Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. Improved approximation algorithms and lower bounds for search-diversification problems. In49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2022

    work page 2022

  2. [2]

    Geometric knapsack problems.Algorithmica, 10(5):399–427, 1993

    Esther M Arkin, Samir Khuller, and Joseph SB Mitchell. Geometric knapsack problems.Algorithmica, 10(5):399–427, 1993

    work page 1993

  3. [3]

    Fair near neighbor search: Independent range sampling in high dimensions

    Martin Aumüller, Rasmus Pagh, and Francesco Silvestri. Fair near neighbor search: Independent range sampling in high dimensions. InProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 191–204, 2020

    work page 2020

  4. [4]

    Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

    Per Austrin, Ioana O Bercea, Mayank Goswami, Nutan Limaye, and Adarsh Srinivasan. Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments. InICALP, 2025

    work page 2025

  5. [5]

    Approximation algorithms for NP-complete problems on planar graphs.Journal of the ACM (JACM), 41(1):153–180, 1994

    Brenda S Baker. Approximation algorithms for NP-complete problems on planar graphs.Journal of the ACM (JACM), 41(1):153–180, 1994

    work page 1994

  6. [6]

    Diversity of solutions: An exploration through the lens of fixed- parameter tractability theory.Artificial Intelligence, 303:103644, 2022

    Julien Baste, Michael R Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A Rosamond. Diversity of solutions: An exploration through the lens of fixed- parameter tractability theory.Artificial Intelligence, 303:103644, 2022

    work page 2022

  7. [7]

    FPT algorithms for diverse collections of hitting sets.Algorithms, 12(12):254, 2019

    Julien Baste, Lars Jaffke, Tomáš Masařík, Geevarghese Philip, and Günter Rote. FPT algorithms for diverse collections of hitting sets.Algorithms, 12(12):254, 2019

    work page 2019

  8. [8]

    Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM), 9(1):61–63, 1962

    Richard Bellman. Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM), 9(1):61–63, 1962

    work page 1962

Show all 61 references
  1. [9]

    Bodlaender

    Hans L. Bodlaender. Planar graphs with bounded treewidth. Technical Report RUU-CS-88-14, Depart- ment of Computer Science, Utrecht University, the Netherlands, 1988

    1988

  2. [10]

    A.E. Brouwer. Table of general binary codes, 2023. Published electronically athttps://www.win.tue. nl/~aeb/codes/binary.html

    2023

  3. [11]

    Brouwer, J.B

    A.E. Brouwer, J.B. Shearer, N.J.A. Sloane, and W.D. Smith. A new table of constant weight codes. IEEE Transactions on Information Theory, 36(6):1334–1380, 1990

    1990

  4. [12]

    An improved analysis of local search for MAX-SUM diversification

    Alfonso Cevallos, Friedrich Eisenbrand, and Rico Zenklusen. An improved analysis of local search for MAX-SUM diversification. Mathematics of Operations Research, 44(4):1494–1509, 2019

    2019

  5. [13]

    Springer, 2015

    Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized algorithms. Springer, 2015

    2015

  6. [14]

    Finding diverse minimum s-t cuts

    Mark de Berg, Andrés López Martínez, and Frits Spieksma. Finding diverse minimum s-t cuts. In34th International Symposium on Algorithms and Computation, 2023

    2023

  7. [15]

    The bidimensionality theory and its algorithmic applications

    Erik D Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51(3):292–302, 2008

    2008

  8. [16]

    Analysis of evolutionary diversity optimization for permutation problems.ACM Transactions on Evolutionary Learning, 2(3):1–27, 2022

    Anh Do, Mingyu Guo, Aneta Neumann, and Frank Neumann. Analysis of evolutionary diversity optimization for permutation problems.ACM Transactions on Evolutionary Learning, 2(3):1–27, 2022

    2022

  9. [17]

    Evolving diverse sets of tours for the travelling salesperson problem

    Anh Viet Do, Jakob Bossek, Aneta Neumann, and Frank Neumann. Evolving diverse sets of tours for the travelling salesperson problem. InProceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 681–689, 2020

    2020

  10. [18]

    Data-driven solution portfolios

    Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassil- vitskii. Data-driven solution portfolios. In16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 46–1. Schloss Dagstuhl–Leibniz-Zentrum für Informat...

    2025

  11. [19]

    Determinantal sieving

    Eduard Eiben, Tomohiro Koana, and Magnus Wahlström. Determinantal sieving. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377–423. SIAM, 2024

    2024

  12. [20]

    Diverse pairs of matchings

    Fedor V Fomin, Petr A Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse pairs of matchings. In31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020

    2020

  13. [21]

    Diverse collections in matroids and graphs.Mathematical Programming, pages 1–33, 2023

    Fedor V Fomin, Petr A Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse collections in matroids and graphs.Mathematical Programming, pages 1–33, 2023

    2023

  14. [22]

    Parameterized complexity of finding dissimilar shortest paths

    Ryo Funayama, Yasuaki Kobayashi, and Takeaki Uno. Parameterized complexity of finding dissimilar shortest paths. arXiv preprint arXiv:2402.14376, 2024

    2024 arXiv

  15. [23]

    Approximation schemes for packing problems withℓp-norm diversity constraints

    Waldo Gálvez and Víctor Verdugo. Approximation schemes for packing problems withℓp-norm diversity constraints. In Latin American Symposium on Theoretical Informatics, pages 204–221. Springer, 2022

    2022

  16. [24]

    Obtaining approximately optimal and diverse solutions via dispersion

    Jie Gao, Mayank Goswami, CS Karthik, Meng-Tsung Tsai, Shih-Yu Tsai, and Hao-Tsung Yang. Obtaining approximately optimal and diverse solutions via dispersion. InLatin American Symposium on Theoretical Informatics, pages 222–239. Springer, 2022

    2022

  17. [25]

    freeman San Francisco, 1979

    Michael R Garey and David S Johnson.Computers and intractability, volume 174. freeman San Francisco, 1979

    1979

  18. [26]

    Approximating geometric knapsack via l-packings.ACM Trans

    Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings.ACM Trans. Algorithms, 17(4):33:1–33:67, 2021

    2021

  19. [27]

    A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

    Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi. A framework to design approximation algorithms for finding diverse solutions in combinatorial problems. In Brian Williams, Yiling Chen, and Jennifer Neville, editors,Thirty-Se...

    2023

  20. [28]

    Computing diverse shortest paths efficiently: A theoretical and experimental study

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, and Yota Otachi. Computing diverse shortest paths efficiently: A theoretical and experimental study. InThirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, pages 3758–3766. AAAI Press, 2022

    2022

  21. [29]

    Finding diverse trees, paths, and more

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, and Yota Otachi. Finding diverse trees, paths, and more. InThirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pages 3778–3786. AAAI Press, 2021

    2021

  22. [30]

    A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied mathematics, 10(1):196–210, 1962

    Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied mathematics, 10(1):196–210, 1962

    1962

  23. [31]

    Efficient planarity testing.Journal of the ACM (JACM), 21(4):549–568, 1974

    John Hopcroft and Robert Tarjan. Efficient planarity testing.Journal of the ACM (JACM), 21(4):549–568, 1974

    1974

  24. [32]

    Ibarra and Chul E

    Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM, 22(4):463–468, 1975

    1975

  25. [33]

    Maximizing the lifetime of wireless sensor networks through domatic partition

    Kamrul Islam, Selim G Akl, and Henk Meijer. Maximizing the lifetime of wireless sensor networks through domatic partition. In2009 IEEE 34th Conference on Local Computer Networks, pages 436–442. IEEE, 2009

    2009

  26. [35]

    Coffman Jr., M

    Edward G. Coffman Jr., M. R. Garey, David S. Johnson, and Robert Endre Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms.SIAM J. Comput., 9(4):808–826, 1980

    1980

  27. [36]

    Pearson, 2005

    Jon Kleinberg and Eva Tardos.Algorithm Design. Pearson, 2005. 16

    2005

  28. [37]

    Max-distance sparsification for diversification and clustering

    Soh Kumabe. Max-distance sparsification for diversification and clustering. arXiv preprint arXiv:2411.02845, 2024

    2024 arXiv

  29. [38]

    E.L. Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem.Management Science, pages 401–405, 1972

    1972

  30. [39]

    A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979

    Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979

    1979

  31. [40]

    On the parameterized complexity of diverse sat

    Neeldhara Misra, Harshil Mittal, and Ashutosh Rai. On the parameterized complexity of diverse sat. In 35th International Symposium on Algorithms and Computation, 2024

    2024

  32. [41]

    M. Plotkin. Binary codes with specified minimum distance.IRE Transactions on Information Theory, 6(4):445–450, 1960

    1960

  33. [42]

    Finding multiple optimal solutions to an integer linear program by random perturbations of its objective function

    Noah Schulhof, Pattara Sukprasert, Eytan Ruppin, Samir Khuller, and Alejandro A Schäffer. Finding multiple optimal solutions to an integer linear program by random perturbations of its objective function. Algorithms, 18(3):140, 2025

    2025

  34. [43]

    Finding diverse strings and longest common subsequences in a graph

    Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, and Hiroki Arimura. Finding diverse strings and longest common subsequences in a graph. In35th Annual Symposium on Combinatorial Pattern Matching, 2024

    2024

  35. [44]

    Complexity of two perfect matchings with minimum shared edges? URL: https://cstheory.stackexchange.com/questions/1278/ complexity-of-two-perfect-matchings-with-minimum-shared-edges

    Jukka Suomela. Complexity of two perfect matchings with minimum shared edges? URL: https://cstheory.stackexchange.com/questions/1278/ complexity-of-two-perfect-matchings-with-minimum-shared-edges

  36. [45]

    Dominating set, independent set, discretek-center, dispersion, and related problems for planar points in convex position

    Anastasiia Tkachenko and Haitao Wang. Dominating set, independent set, discretek-center, dispersion, and related problems for planar points in convex position. InSTACS, 2025

    2025

  37. [46]

    Springer, 2001

    Vijay V Vazirani.Approximation Algorithms. Springer, 2001

    2001

  38. [47]

    Linear degree extractors and the inapproximability of max clique and chromatic number

    David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput., 3(1):103–128, 2007. 17 A Full Proof for Theorem 5 (Diverse Knapsack) We first restate the theorem for the reader’s convenience, and then present the full pro...

    2007

  39. [48]

    algorithm with(1 − δ)-RA

    An O(n5k5/δ)-time max{1/2, 1 − 2/(k + 1)}-APX. algorithm with(1 − δ)-RA

  40. [49]

    algorithm with (1 − δ)-RA

    An k5nO(ε−1)f (δ, ε, γ)-time (1 − ε)-APX. algorithm with (1 − δ)-RA. whose output solutions each have weight at most(1 + γ)W. That is, the problem admits a PTAS when we allow a small capacity violation. Note that the search spaces for (1) and (2) of Theorem 5 are a bit differe...

  41. [50]

    The knapsack region[0, N] × [0, N] can be decomposed into at mostKε ∈ Oε(1) rectangular subregions whose dimensions belong to a set that can be efficiently computed just by knowing the instance, such that each item in the solution belongs to one of the regions

  42. [51]

    Definition 22

    Each subregion is either a horizontal container, where items are placed one on top of the other, or a vertical container, where items are placed one next to the other, or an area container, where items are placed by means ofNFDH, and they satisfy that their widths and heights ...

  43. [52]

    The values ofH and W belong to a set that can be efficiently computed just by knowing the instance

    The knapsack region[0, N]×[0, N] can be decomposed into two subregions, where one of them is a rectangular subregion of widthW ≤ N and height H ≤ N anchored at the top-right corner of the knapsack, and the other one is the complement (i.e., aL-shaped region). The values ofH an...

  44. [53]

    The rectangular subregion contains solely items of height and width at most some parameterℓ, which belongs to a set that can be efficiently computed just by knowing the instance, and theL-shaped region contains solely items whose longer side has length at leastℓ

  45. [54]

    See Figure 4 for examples of container-based andL&C-based packings

    The rectangular subregion is a container-based packing, while theL-shaped region is anL-packing, meaning that items are partitioned into vertical and horizontal depending on their longer dimension, satisfying that the horizontal side of theL-shaped region has horizontal items ...

  46. [55]

    For eachi ∈ [k], Pi ∈ SL

  47. [56]

    For eachi ∈ [k], v(Pi) ≥ c · maxS∈SL v(S)

  48. [57]

    P i̸=j∈[k] |Pi∆Pj| is maximized. As a partial application to our framework (Corollary 10), we prove that there is amax{1/2, 1 − 2/(k + 1)}- approximation algorithm for(1−δ)c-resource augmentation algorithm for theDiverse Enclosing-Polygons problem, by adapting the dynamic prog...

  49. [58]

    the enclosure lies within the halfplaneHij (left to the oriented line− →ij), and

  50. [59]

    pipj is an edge of the enclosing polygon. Then, ℓ(s, pi, pj, ˜v) is defined recursively by min h: ph∈Hij , h̸=i,j n ℓ s − s(△ijh) + si + sh , pi, ph, ˜v − ˜v(△ijh) + ˜vi + ˜vh + (ℓij + ℓjh − ℓih) o , where ˜v(△ijh) (resp., s(△ijh) represents the sum of the (adjusted) values (r...

  51. [60]

    ℓ(s, pi, pj, ˜v) = ∞ if ˜v ̸= P h: ph∈Hij ˜vh or s ̸= P h: ph∈Hij sh

  52. [61]

    We computemini̸=j ℓ(s, pi, pj, ˜V ) in order of increasing˜v and s, for ˜v = 1,

    2lij if ˜vi + ˜vj = ˜v and si + sj = s. We computemini̸=j ℓ(s, pi, pj, ˜V ) in order of increasing˜v and s, for ˜v = 1, . . . ,˜V and for s = 1, . . . , nk, and find mini̸=j ℓ(s, pi, pj, ˜V ) < ∞ with the largest possible value ofs. If mini̸=j ℓ(s, pi, pj, ˜V ) = ∞ for all s, ...

  53. [62]

    If there are less thank such tours, the rest of the components ofLk(W ′, i, S) is filled with∞

    ≤ · · · ≤ℓ(T ′ k) ≤ ℓ(T ) for anyc-optimal TSP tourT with weightW ′ that has starts at vertex 1 and ends at vertexi ∈ S ⊆ V \ {1}. If there are less thank such tours, the rest of the components ofLk(W ′, i, S) is filled with∞. Then, Lk(W ′, i, S) can be computed by choosing th...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.