pith. sign in

arxiv: 2607.00843 · v1 · pith:UHOOZSPLnew · submitted 2026-07-01 · 💻 cs.DS

Submodular Maximization over Many Matroids via Ordered Local Search

Neta Singer , Theophile Thiery This is my paper

Pith reviewed 2026-07-02 04:29 UTC · model grok-4.3

classification 💻 cs.DS
keywords submodular maximizationmatroid intersectionlocal searchapproximation algorithmsk-matroidsset packingmatroid parity
0
0 comments X

The pith

A polynomial-time ordered local search achieves k/2 + o(k) approximation for monotone submodular maximization over k matroids.

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

The paper develops a local-search algorithm that orders candidate elements by decreasing marginal value and performs swaps only when their gain exceeds a k-dependent threshold. This procedure runs in polynomial time and delivers a k/2 + o(k) guarantee, asymptotically matching the prior best result known only for the unweighted case. The same bound holds for the matroid k-parity problem. For weighted k-set packing the authors combine the ordering idea with weight bucketing to reach ln(4)k/3 + o(k), improving the previous ratio.

Core claim

Processing elements greedily in decreasing order of marginal value and searching for sufficiently profitable swaps whose gain exceeds a parameter alpha given as a function of k yields a polynomial-time algorithm with approximation ratio k/2 + o(k) for the maximum of a monotone submodular function over the intersection of k matroids; the identical guarantee extends to matroid k-parity.

What carries the argument

Ordered local search that processes elements in decreasing marginal-value order and performs swaps whose gain exceeds the k-dependent threshold alpha(k).

If this is right

  • The algorithm matches the best known guarantee for the unweighted setting and applies to the weighted setting as well.
  • The identical ratio holds for matroid k-parity.
  • Combining the ordering with weight bucketing produces a ln(4)k/3 + o(k) guarantee for weighted k-set packing.
  • This improves on the earlier ln(4)k/(1+ln 2) + o(k) bound obtained via pure weight bucketing.

Where Pith is reading between the lines

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

  • The ordering step may simplify analysis of local search for other intersection problems where marginal gains provide a natural total order.
  • Refining the choice of alpha(k) could tighten the o(k) term or produce explicit constants for moderate k.
  • The method suggests that ordering by marginal value can substitute for bucketing in some submodular settings, potentially reducing implementation complexity.

Load-bearing premise

The local-search procedure can be implemented to run in polynomial time while correctly identifying and performing swaps whose gain exceeds the k-dependent threshold alpha(k).

What would settle it

An explicit instance of k matroids and a monotone submodular function on which every sequence of ordered swaps either fails to reach value at least (k/2 + o(k)) times optimum or requires superpolynomial time.

read the original abstract

Given a monotone submodular function, we consider the problem of finding a maximum-valued set in the intersection of $k$ matroids. Our main result is a polynomial time local search based algorithm achieving a $\frac{k}{2} + o(k)$ approximation guarantee. This asymptotically matches the best-known guarantee of $\frac{k}{2} + \epsilon$ in the unweighted setting by Lee, Sviridenko, and Vondr\'ak (2009). Prior to this work, the state-of-the-art was a $\frac{\ln(4)k}{1+\ln(2)} + o(k)$-approximation algorithm obtained by Feldman and Ward (2026). Our approach extends to Matroid $k$-Parity yielding the same approximation guarantee. In contrast to the weight bucketing approach underlying the recent advances of Singer and Thiery (2025) and Feldman and Ward (2026), our algorithm processes elements greedily in decreasing order of marginal value and searches for sufficiently profitable swaps, whose gain exceeds a parameter $\alpha$ given as a function of $k$. We further combine this idea with the weight bucketing approach to obtain improved guarantees for weighted $k$-Set Packing. Our second main result is a $\frac{\ln(4)k}{3} + o(k)$-approximation algorithm for weighted $k$-Set Packing, improving on the state of the art $\frac{k}{2.00561} + O(1)$-approximation by Neuwohner (2023).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript presents an ordered local-search algorithm for maximizing a monotone submodular function subject to the intersection of k matroids. Elements are processed in decreasing order of marginal value, and improving swaps are accepted only when their gain exceeds a k-dependent threshold α(k). The central claim is a polynomial-time (k/2 + o(k))-approximation that asymptotically matches the best known guarantee for the unweighted case; the same guarantee is claimed for the matroid k-parity problem. A secondary result combines the approach with weight bucketing to obtain a (ln(4)k/3 + o(k))-approximation for weighted k-set packing, improving on prior work.

Significance. If the polynomial-time claim and approximation guarantees are established with complete proofs, the result would be significant: it supplies an asymptotically tight local-search algorithm for multi-matroid submodular maximization that avoids the weight-bucketing paradigm of recent papers and simultaneously improves the ratio for weighted k-set packing. The explicit use of an ordered processing order together with a tunable threshold is a technically distinct contribution.

major comments (2)
  1. [Abstract] Abstract (algorithm paragraph): the polynomial-time claim requires an explicit potential-function argument showing that the number of accepted swaps is polynomially bounded when the per-swap gain is at least α(k). If α(k) = o(1/k), the iteration count could become super-polynomial; no such bound or choice of α(k) is exhibited.
  2. [Abstract] Abstract (algorithm paragraph) and Matroid k-Parity extension: each candidate swap must be discoverable with polynomially many independence-oracle calls while respecting the ordering and the threshold α(k). The abstract supplies neither the search procedure nor its oracle complexity, which is load-bearing for both the main result and the parity extension.
minor comments (1)
  1. [Abstract] The abstract states the o(k) term without indicating the dependence on k or the hidden constants; a more precise statement of the approximation ratio (even if asymptotic) would aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation for major revision. The comments highlight opportunities to improve the clarity of the abstract regarding the polynomial-time guarantees. We address each point below and will revise the abstract accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (algorithm paragraph): the polynomial-time claim requires an explicit potential-function argument showing that the number of accepted swaps is polynomially bounded when the per-swap gain is at least α(k). If α(k) = o(1/k), the iteration count could become super-polynomial; no such bound or choice of α(k) is exhibited.

    Authors: The full manuscript (Section 3) selects α(k) = Θ(1/k²) and supplies an explicit potential-function argument: define Φ(S) = f(S) + (α(k)/2)·|S|; each accepted swap increases Φ by at least α(k)/2, while Φ is bounded above by O(f(OPT)), yielding at most O(n/α(k)) iterations and hence polynomial runtime. The abstract omitted these parameters for brevity. We will revise the abstract to state the choice of α(k) and confirm the polynomial bound via the potential function. revision: yes

  2. Referee: [Abstract] Abstract (algorithm paragraph) and Matroid k-Parity extension: each candidate swap must be discoverable with polynomially many independence-oracle calls while respecting the ordering and the threshold α(k). The abstract supplies neither the search procedure nor its oracle complexity, which is load-bearing for both the main result and the parity extension.

    Authors: Section 4 details the ordered search: elements are sorted by marginal value; for each element we enumerate O(n) candidate swaps and verify feasibility with O(k) independence-oracle calls per swap while enforcing the gain threshold α(k). Total oracle complexity is O(n²k). The identical procedure and complexity bound extend to the matroid k-parity problem (Section 5). We will revise the abstract to note that swaps are found via a polynomial number of oracle calls respecting the order and threshold. revision: yes

Circularity Check

0 steps flagged

Algorithmic construction independent of fitted inputs or self-citation chains

full rationale

The paper presents an explicit local-search procedure (ordered processing by marginal value plus thresholded swaps with parameter α(k)) whose approximation analysis and polynomial-time claim are stated as direct consequences of the algorithm definition and standard matroid oracle properties. No equations reduce a claimed prediction to a fitted constant, and the cited prior works (including the authors' 2025 paper) are invoked only for contrast, not as load-bearing uniqueness theorems or ansatzes. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definitions of monotone submodularity and matroid intersection; no free parameters, new entities, or non-standard axioms are introduced in the abstract.

axioms (2)
  • domain assumption The objective function is monotone and submodular.
    Standard problem assumption stated in the first sentence of the abstract.
  • domain assumption The k matroids are provided as input and their independence oracles are available.
    Implicit in the problem statement of finding a maximum-valued set in the intersection of k matroids.

pith-pipeline@v0.9.1-grok · 5805 in / 1352 out tokens · 33060 ms · 2026-07-02T04:29:20.451779+00:00 · methodology

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

300 extracted references · 109 canonical work pages · 6 internal anchors

  1. [1]

    International Conference on Machine Learning , pages=

    Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    2019

  2. [2]

    A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems , booktitle =

    Justin Ward , editor =. A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems , booktitle =. 2012 , url =. doi:10.4230/LIPICS.STACS.2012.42 , timestamp =

    work page doi:10.4230/lipics.stacs.2012.42 2012

  3. [3]

    2026 , eprint=

    Submodular Maximization over a Matroid k -Intersection: Multiplicative Improvement over Greedy , author=. 2026 , eprint=

    2026

  4. [4]

    Streaming submodular maximization: massive data summarization on the fly , booktitle =

    Ashwinkumar Badanidiyuru and Baharan Mirzasoleiman and Amin Karbasi and Andreas Krause , editor =. Streaming submodular maximization: massive data summarization on the fly , booktitle =. 2014 , url =. doi:10.1145/2623330.2623637 , timestamp =

    work page doi:10.1145/2623330.2623637 2014

  5. [5]

    Approximate multi-matroid intersection via iterative refinement , journal =

    Andr. Approximate multi-matroid intersection via iterative refinement , journal =. 2020 , url =. doi:10.1007/S10107-020-01524-Y , timestamp =

    work page doi:10.1007/s10107-020-01524-y 2020

  6. [6]

    Mathematical programming , volume=

    On linear and semidefinite programming relaxations for hypergraph matching , author=. Mathematical programming , volume=. 2012 , publisher=

    2012

  7. [7]

    Journal of Combinatorial Theory, Series B , volume=

    Fractional matroid matchings , author=. Journal of Combinatorial Theory, Series B , volume=. 1992 , publisher=

    1992

  8. [8]

    Journal of Combinatorial Theory, Series B , volume=

    An algorithm for weighted fractional matroid matching , author=. Journal of Combinatorial Theory, Series B , volume=. 2013 , publisher=

    2013

  9. [9]

    Proceedings of the London Mathematical Society , volume=

    Note on independence functions , author=. Proceedings of the London Mathematical Society , volume=. 1957 , publisher=

    1957

  10. [10]

    Submodular Functions, Matroids, and Certain Polyhedra , url =

    Edmonds, Jack , booktitle =. Submodular Functions, Matroids, and Certain Polyhedra , url =. 2003 , bdsk-url-1 =. doi:10.1007/3-540-36478-1_2 , editor =

    work page doi:10.1007/3-540-36478-1_2 2003

  11. [11]

    Journal of Combinatorial Theory , volume=

    Optimal assignments in an ordered set: an application of matroid theory , author=. Journal of Combinatorial Theory , volume=. 1968 , publisher=

    1968

  12. [12]

    Streaming Algorithms for Submodular Function Maximization , booktitle =

    Chandra Chekuri and Shalmoli Gupta and Kent Quanrud , editor =. Streaming Algorithms for Submodular Function Maximization , booktitle =. 2015 , url =. doi:10.1007/978-3-662-47672-7\_26 , timestamp =

    work page doi:10.1007/978-3-662-47672-7 2015

  13. [13]

    A weighted linear matroid parity algorithm , booktitle =

    Satoru Iwata and Yusuke Kobayashi , editor =. A weighted linear matroid parity algorithm , booktitle =. 2017 , url =. doi:10.1145/3055399.3055436 , timestamp =

    work page doi:10.1145/3055399.3055436 2017

  14. [14]

    ACM Transactions on Algorithms (TALG) , volume=

    Algebraic algorithms for linear matroid parity problems , author=. ACM Transactions on Algorithms (TALG) , volume=. 2014 , publisher=

    2014

  15. [15]

    Jensen and Bernhard Korte , title =

    Per M. Jensen and Bernhard Korte , title =. 1982 , url =. doi:10.1137/0211014 , timestamp =

    work page doi:10.1137/0211014 1982

  16. [16]

    Matroid matching and some applications , journal =

    L. Matroid matching and some applications , journal =. 1980 , url =. doi:10.1016/0095-8956(80)90066-0 , timestamp =

    work page doi:10.1016/0095-8956(80)90066-0 1980

  17. [17]

    2001 , publisher=

    Combinatorial optimization: networks and matroids , author=. 2001 , publisher=

    2001

  18. [18]

    Greedy Local Improvement and Weighted Set Packing Approximation , booktitle =

    Barun Chandra and Magn. Greedy Local Improvement and Weighted Set Packing Approximation , booktitle =. 1999 , url =

    1999

  19. [19]

    Proceedings of the Fourteenth Annual

    Piotr Berman and Piotr Krysta , title =. Proceedings of the Fourteenth Annual. 2003 , url =

    2003

  20. [20]

    An Improved Approximation for Maximum Weighted

    Theophile Thiery and Justin Ward , editor =. An Improved Approximation for Maximum Weighted. Proceedings of the 2023. 2023 , url =. doi:10.1137/1.9781611977554.CH42 , timestamp =

    work page doi:10.1137/1.9781611977554.ch42 2023

  21. [21]

    An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs , booktitle =

    Meike Neuwohner , editor =. An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs , booktitle =. 2021 , url =. doi:10.4230/LIPICS.STACS.2021.53 , timestamp =

    work page doi:10.4230/lipics.stacs.2021.53 2021

  22. [22]

    The Limits of Local Search for Weighted k-Set Packing , booktitle =

    Meike Neuwohner , editor =. The Limits of Local Search for Weighted k-Set Packing , booktitle =. 2022 , url =. doi:10.1007/978-3-031-06901-7\_31 , timestamp =

    work page doi:10.1007/978-3-031-06901-7 2022

  23. [23]

    Passing the Limits of Pure Local Search for Weighted

    Meike Neuwohner , editor =. Passing the Limits of Pure Local Search for Weighted. Proceedings of the 2023. 2023 , url =. doi:10.1137/1.9781611977554.CH41 , timestamp =

    work page doi:10.1137/1.9781611977554.ch41 2023

  24. [24]

    54th Annual

    Marek Cygan , title =. 54th Annual. 2013 , url =. doi:10.1109/FOCS.2013.61 , timestamp =

    work page doi:10.1109/focs.2013.61 2013

  25. [25]

    2003 , publisher=

    Combinatorial optimization: polyhedra and efficiency , author=. 2003 , publisher=

    2003

  26. [26]

    Scandinavian Workshop on Algorithm Theory , pages=

    A d/2 approximation for maximum weight independent set in d-claw free graphs , author=. Scandinavian Workshop on Algorithm Theory , pages=. 2000 , organization=

    2000

  27. [27]

    SIAM Journal on Computing , volume=

    Matroid matching: the power of local search , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  28. [28]

    arXiv preprint arXiv:2409.17831 , year=

    Asymptotically Optimal Hardness for k -Set Packing and k -Matroid Intersection , author=. arXiv preprint arXiv:2409.17831 , year=

    work page arXiv

  29. [29]

    Michal Lason , title =. Eur. J. Comb. , volume =. 2015 , url =. doi:10.1016/J.EJC.2015.04.004 , timestamp =

    work page doi:10.1016/j.ejc.2015.04.004 2015

  30. [30]

    Proceedings of the twenty-fourth annual acm-siam symposium on discrete algorithms , pages=

    How to sell hyperedges: The hypermatching assignment problem , author=. Proceedings of the twenty-fourth annual acm-siam symposium on discrete algorithms , pages=. 2013 , organization=

    2013

  31. [31]

    SIAM Journal on Computing , volume=

    A tight linear time (1/2)-approximation for unconstrained submodular maximization , author=. SIAM Journal on Computing , volume=. 2015 , publisher=

    2015

  32. [32]

    International Symposium on Combinatorial Optimization , pages=

    Approximating the-set packing problem by local improvements , author=. International Symposium on Combinatorial Optimization , pages=. 2014 , organization=

    2014

  33. [33]

    International colloquium on automata, languages, and programming , pages=

    Large neighborhood local search for the maximum set packing problem , author=. International colloquium on automata, languages, and programming , pages=. 2013 , organization=

    2013

  34. [34]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Better Approximation for Weighted k-Matroid Intersection , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  35. [35]

    2010 , publisher=

    Matroid theory , author=. 2010 , publisher=

    2010

  36. [36]

    ORSA Journal on Computing , volume=

    Matroid applications and algorithms , author=. ORSA Journal on Computing , volume=. 1992 , publisher=

    1992

  37. [37]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    A 5/4-Approximation for Two-Edge Connectivity , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  38. [38]

    2009 , url =

    Nikhil Bansal and Rohit Khandekar and Viswanath Nagarajan , title =. 2009 , url =. doi:10.1137/080734340 , timestamp =

    work page doi:10.1137/080734340 2009

  39. [39]

    Combinatorica , volume=

    A factor 2 approximation algorithm for the generalized Steiner network problem , author=. Combinatorica , volume=. 2001 , publisher=

    2001

  40. [40]

    On generalizations of network design problems with degree bounds , journal =

    Nikhil Bansal and Rohit Khandekar and Jochen K. On generalizations of network design problems with degree bounds , journal =. 2013 , url =. doi:10.1007/S10107-012-0537-8 , timestamp =

    work page doi:10.1007/s10107-012-0537-8 2013

  41. [41]

    Submodular Maximization with Cardinality Constraints , booktitle =

    Niv Buchbinder and Moran Feldman and Joseph Naor and Roy Schwartz , editor =. Submodular Maximization with Cardinality Constraints , booktitle =. 2014 , url =. doi:10.1137/1.9781611973402.106 , timestamp =

    work page doi:10.1137/1.9781611973402.106 2014

  42. [42]

    2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=

    Approximation algorithms for allocation problems: Improving the factor of 1-1/e , author=. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=. 2006 , organization=

    2006

  43. [43]

    Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

    Submodular function maximization via the multilinear relaxation and contention resolution schemes , author=. Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

  44. [44]

    Varadarajan and Zhao Zhang , title =

    Chandra Chekuri and Tanmay Inamdar and Kent Quanrud and Kasturi R. Varadarajan and Zhao Zhang , title =. J. Comb. Optim. , volume =. 2022 , url =. doi:10.1007/S10878-022-00874-X , timestamp =

    work page doi:10.1007/s10878-022-00874-x 2022

  45. [45]

    2023 , url =

    Jugal Garg and Pooja Kulkarni and Rucha Kulkarni , title =. 2023 , url =. doi:10.1145/3613452 , timestamp =

    work page doi:10.1145/3613452 2023

  46. [46]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Set covering with our eyes wide shut , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  47. [47]

    2024 , note =

    2024 Summer Workshop Program , howpublished =. 2024 , note =

    2024

  48. [48]

    2025 , note =

    TAAP25: Theory and Applications of Algorithms with Predictions , howpublished =. 2025 , note =

    2025

  49. [49]

    Algorithms with Predictions

    Workshop on “Algorithms with Predictions” at. 2022 , note =

    2022

  50. [50]

    2025 , urldate =

    Learning-augmented Algorithms: Theory & Applications , howpublished =. 2025 , urldate =

    2025

  51. [51]

    2021 , note =

    Machine Learning for Algorithms (ML4A) Workshop , howpublished =. 2021 , note =

    2021

  52. [52]

    Algorithms with Predictions

    Workshop on “Algorithms with Predictions” (ALPS 2022) , howpublished =. 2022 , note =

    2022

  53. [53]

    arXiv preprint arXiv:2102.07011 , year=

    Beating two-thirds for random-order streaming matching , author=. arXiv preprint arXiv:2102.07011 , year=

    work page arXiv

  54. [54]

    arXiv preprint arXiv:2305.01070 , year=

    Robust communication complexity of matching: EDCS achieves 5/6 approximation , author=. arXiv preprint arXiv:2305.01070 , year=

    work page arXiv

  55. [55]

    arXiv preprint arXiv:2412.00717 , year=

    Data-driven solution portfolios , author=. arXiv preprint arXiv:2412.00717 , year=

    work page arXiv

  56. [56]

    Mathematical Programming , volume=

    Towards an optimal contention resolution scheme for matchings , author=. Mathematical Programming , volume=. 2025 , publisher=

    2025

  57. [57]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Submodular function maximization in parallel via the multilinear relaxation , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  58. [58]

    SIAM Journal on Computing , volume=

    Matroid secretary problem in the random-assignment model , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  59. [59]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  60. [60]

    Research Trends in Combinatorial Optimization: Bonn 2008 , pages=

    Theory of principal partitions revisited , author=. Research Trends in Combinatorial Optimization: Bonn 2008 , pages=. 2009 , publisher=

    2008

  61. [61]

    Mathematical Programming , volume=

    An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint , author=. Mathematical Programming , volume=. 2022 , publisher=

    2022

  62. [62]

    Nguyen , editor =

    Alina Ene and Huy L. Nguyen , editor =. Constrained Submodular Maximization: Beyond 1/e , booktitle =. 2016 , url =. doi:10.1109/FOCS.2016.34 , timestamp =

    work page doi:10.1109/focs.2016.34 2016

  63. [63]

    Ageev and Maxim Sviridenko , title =

    Alexander A. Ageev and Maxim Sviridenko , title =. J. Comb. Optim. , volume =. 2004 , url =. doi:10.1023/B:JOCO.0000038913.96607.C2 , timestamp =

    work page doi:10.1023/b:joco.0000038913.96607.c2 2004

  64. [64]

    Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal =

    Gruia C. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal =. 2011 , url =. doi:10.1137/080733991 , timestamp =

    work page doi:10.1137/080733991 2011

  65. [65]

    Tight FPT Approximations for $k$-Median and $k$-Means

    Tight FPT Approximations for k -Median and k -Means , author=. arXiv preprint arXiv:1904.12334 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  66. [66]

    arXiv preprint arXiv:2404.08972 , year=

    Improved approximations for flexible network design , author=. arXiv preprint arXiv:2404.08972 , year=

    work page arXiv

  67. [67]

    Journal of the ACM (JACM) , volume=

    A threshold of ln n for approximating set cover , author=. Journal of the ACM (JACM) , volume=. 1998 , publisher=

    1998

  68. [68]

    Approximating minimum bounded degree spanning trees to within one of optimal , booktitle =

    Mohit Singh and Lap Chi Lau , editor =. Approximating minimum bounded degree spanning trees to within one of optimal , booktitle =. 2007 , url =. doi:10.1145/1250790.1250887 , timestamp =

    work page doi:10.1145/1250790.1250887 2007

  69. [69]

    Goemans , title =

    Michel X. Goemans , title =. 47th Annual. 2006 , url =. doi:10.1109/FOCS.2006.48 , timestamp =

    work page doi:10.1109/focs.2006.48 2006

  70. [70]

    Approximating the Minimum-Degree Steiner Tree to within One of Optimal , journal =

    Martin F. Approximating the Minimum-Degree Steiner Tree to within One of Optimal , journal =. 1994 , url =. doi:10.1006/JAGM.1994.1042 , timestamp =

    work page doi:10.1006/jagm.1994.1042 1994

  71. [71]

    SIAM Journal on Computing , volume=

    Improved bounds for matroid partition and intersection algorithms , author=. SIAM Journal on Computing , volume=. 1986 , publisher=

    1986

  72. [72]

    Mathematical programming , volume=

    Matroid intersection algorithms , author=. Mathematical programming , volume=. 1975 , publisher=

    1975

  73. [73]

    Naval research logistics quarterly , volume=

    The Hungarian method for the assignment problem , author=. Naval research logistics quarterly , volume=. 1955 , publisher=

    1955

  74. [74]

    2006 , publisher=

    Matroid theory , author=. 2006 , publisher=

    2006

  75. [75]

    arXiv preprint arXiv:2409.17831 , year=

    Euiwoong Lee and Ola Svensson and Theophile Thiery , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2409.17831 , eprinttype =. 2409.17831 , timestamp =

    work page doi:10.48550/arxiv.2409.17831 2024

  76. [76]

    Better Approximation for Weighted k-Matroid Intersection , booktitle =

    Neta Singer and Theophile Thiery , editor =. Better Approximation for Weighted k-Matroid Intersection , booktitle =. 2025 , url =. doi:10.1145/3717823.3718219 , timestamp =

    work page doi:10.1145/3717823.3718219 2025

  77. [77]

    Electron

    Piotr Berman and Marek Karpinski , title =. Electron. Colloquium Comput. Complex. , volume =. 2003 , url =. TR03-008 , timestamp =

    2003

  78. [78]

    Manshadi and Shayan Oveis Gharan and Amin Saberi , title =

    Vahideh H. Manshadi and Shayan Oveis Gharan and Amin Saberi , title =. Math. Oper. Res. , volume =. 2012 , url =. doi:10.1287/MOOR.1120.0551 , timestamp =

    work page doi:10.1287/moor.1120.0551 2012

  79. [79]

    2001 , publisher=

    Approximation algorithms , author=. 2001 , publisher=

    2001

  80. [80]

    Zhiyi Huang and Ning Kang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang and Xue Zhu , title =. J. 2020 , url =. doi:10.1145/3390890 , timestamp =

    work page doi:10.1145/3390890 2020

Showing first 80 references.