Pith. sign in

REVIEW 6 minor 132 references

Approximation Algorithms for Matroidal Prerequisite Systems

T0 review · 0 major / 6 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read Matroidal prerequisite systems admit efficient approximations whose factors track distance from a pure matroid or pure poset antimatroid.

desk verdict Solid theory paper that cleanly defines MPS, proves the cryptomorphism, and delivers matching two-parameter approximations plus Gap-ETH hardness. read the letter →

arxiv 2607.08151 v1 pith:3BWDR2LC submitted 2026-07-09 cs.DS cs.DM

Robert P. Streit , Vijay K. Garg This is my paper · ORCID
classification cs.DScs.DM MSC 68W2590C2705B35
keywords matroidalprerequisitesystemspolymatroidgreedoidsapproximationalgorithmssubmodularmaximizationmatroidconnectivityposetantimatroidsdensestk-subgraphhardness
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

Many real decisions are blocked by prerequisites, yet the prerequisites are often functional rather than literal: any of several alternative combinations may supply the needed capability. The paper formalizes this interaction as a matroidal prerequisite system (MPS)—a poset that names the prerequisites and a matroid that decides when they have been covered by span—producing an order-sensitive family of feasible sequences. It then supplies polynomial-time approximation algorithms for both additive and monotone submodular maximization over those sequences. The approximation ratios are controlled by two structural parameters that measure how far the MPS sits from a pure matroid (parameter Δ) and from a pure poset antimatroid (parameter λ_max). Exact solutions are recovered in the two classical extremes; the ratios degrade smoothly as the structure becomes more entangled. A matching hardness result shows that substantially better ratios are impossible under a standard complexity hypothesis. The result therefore gives a clean, parameterized way to optimize under interacting independence and substitution constraints that neither pure matroids nor pure precedence models capture.

What carries the argument

The cryptomorphism between matroidal prerequisite systems and strong polymatroid greedoids, together with the fill-in lemma that any sequence of positive marginals under the greatest representation extends to a feasible word by letter insertions.

What would settle it

Exhibit a concrete MPS whose additive optimum cannot be approximated better than min{Δ,λ_max}^{o(1)} by any polynomial-time algorithm, or show that the continuous-greedy scaffolding of Algorithm 3 can be replaced by a procedure whose guarantee improves the Δ^{2} factor.

Watch

Extended reading notes

Core claim

An MPS is cryptomorphic to a strong polymatroid greedoid. Consequently the greatest representation of that greedoid can be evaluated by a single matroid-rank query, and any sequence whose successive marginals under the greatest representation are positive can be filled into a feasible word. These two facts let the authors reduce additive and submodular maximization over MPS words to classical polymatroid or matroid algorithms, obtaining deterministic min{Δ,1+λ_max}-approximations for nonnegative additive objectives and both a deterministic (2+λ_max)-approximation and a randomized Δ^{2}/(1−1/e−δ)-approximation for monotone submodular objectives.

Load-bearing premise

The modeling assumption that whenever a letter is already covered by the matroid span of a feasible word, every one of its prerequisites must also be covered; without this compatibility condition the greatest-representation and fill-in arguments fail.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper introduces matroidal prerequisite systems (MPS), languages of feasible words defined by the interaction of a matroid (encoding substitutable functionality via span) and a poset (encoding prerequisites), subject to a compatibility condition (Eq. 4). It proves a cryptomorphism (Theorem 4.11) between MPS and strong polymatroid greedoids, shows that the greatest representation equals the composition of matroid rank with the ideal operator (Proposition 4.12), and establishes a fill-in/projection lemma (Lemma 4.13). Using these tools it gives efficient deterministic min{Δ, 1+λ_max}-approximations for nonnegative additive maximization and efficient deterministic (2+λ_max)- and randomized (Δ²·(1−1/e−δ)⁻¹)-approximations for monotone submodular maximization over feasible words (Theorems 5.1–6.2). An approximation-preserving reduction from densest k-subgraph shows that, under Gap-ETH, no min{Δ, λ_max}^{o(1)}-approximation exists for the additive case (Lemma 7.1 / Main Result 2).

Significance. The work supplies a clean, order-sensitive constraint model that properly generalizes both matroids and poset antimatroids while retaining enough structure for nontrivial approximation. The two parameters Δ and λ_max give a transparent interpolation between the two classical extremes, and the algorithms recover exact (or essentially best-possible) guarantees in those extremes for additive objectives. The cryptomorphism and the fill-in lemma are reusable technical contributions; the hardness result shows that the dependence on the structural parameters cannot be removed to o(1) under a standard fine-grained hypothesis. The development is self-contained once the definition of strong polymatroid greedoids is granted, and all claims are accompanied by complete combinatorial proofs.

minor comments (6)
  1. The abstract and Main Result 1 state the additive guarantee as min{Δ, 1+λ_max}; the body proves the two bounds separately (Theorems 5.1 and 6.1). A one-sentence remark that the overall algorithm simply runs both and returns the better solution would make the min explicit for the reader.
  2. Section 1 and the discussion after Main Result 1 correctly note that the (2+λ_max) guarantee for submodular maximization does not interpolate to exact optimality when the MPS is a poset antimatroid (λ_max=0). Flagging this more prominently (e.g., as an open question in the introduction) would help set expectations.
  3. Proposition 4.12 and the subsequent algorithms rely on a matroid rank oracle together with ideal computations. A short complexity paragraph (oracle model, number of rank queries per iteration) would make the “efficient” claims fully precise.
  4. Figure 2 is helpful but dense; labeling a few covering relations with the corresponding letters would make the correspondence between flats and flat supports easier to parse on first reading.
  5. Appendix A shows that plain greedy is essentially only an R-approximation. A forward pointer from Remark 4.5 to Appendix A would help readers who stop at the main text.
  6. Minor typographical items: the manuscript date reads “May 6, 2026”; a few places write “nonnegativeadditivemaximization” without spaces in the abstract/hardness paragraph; and “Steinitz-Maclane” is more commonly “Steinitz–Mac Lane.”

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; cryptomorphism and approximation analyses are self-contained, with only non-load-bearing citation of authors' prior greedoid theory.

full rationale

The paper defines MPS from first principles (Def. 4.1 with compatibility Eq. 4), proves it is an optimistic interval greedoid (Prop. 4.8) whose flat supports are closed under intersection (Lemma 4.9), and establishes the cryptomorphism to strong polymatroid greedoids (Thm. 4.11) by explicit construction in both directions. Greatest representation evaluation (Prop. 4.12) and fill-in (Lemma 4.13) follow directly, enabling the scaffolding (Alg. 2–3, Thms. 5.1–5.2) and marginal-adjusted greedy (Alg. 4–5, Thms. 6.1–6.2) analyses via standard submodular/polymatroid arguments. Hardness (Lemma 7.1) is an approximation-preserving reduction from densest k-subgraph under Gap-ETH. The sole self-citation is to [SG26] for the ambient definition of strong polymatroid greedoids and their greatest representation; this is not load-bearing because the equivalence and all algorithmic guarantees are re-derived inside the manuscript without assuming the target approximation ratios. No fitted parameters, self-definitional loops, uniqueness imports, or ansatz smuggling appear. Score 1 reflects only the minor, non-circular self-citation of prior theory.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

Pure combinatorial-optimization theory. No free parameters are fitted. The only non-standard axioms are the definitional requirements that turn a matroid-plus-poset pair into an MPS (compatibility) and the background theory of strong polymatroid greedoids taken from the authors’ earlier note. All other ingredients (matroid rank, submodularity, continuous greedy, Gap-ETH) are standard.

assumptions (4)
  • ad hoc to paper A matroid-plus-poset pair satisfies the compatibility condition (Eq. 4): every letter in the matroid span of a feasible word has all its prerequisites also in that span.
    Imposed by Definition 4.1; required for optimism and for the greatest representation to be well-behaved.
  • domain assumption Strong polymatroid greedoids admit a greatest representation that is a polymatroid rank function and whose span coincides with the kernel closure of the greedoid.
    Taken from the authors’ prior work [SG26]; used throughout Sections 4–6.
  • standard math Continuous greedy plus pipage rounding yields a (1-1/e-δ)-approximation for monotone submodular maximization over matroids (Calinescu et al. 2011).
    Black-box subroutine in Algorithm 3 / Theorem 5.2.
  • standard math Under Gap-ETH there is no |V|^{o(1)}-approximation for Densest-k-Subgraph (Manurangsi 2017).
    Invoked for the hardness reduction in Section 7.
invented entities (2)
  • Matroidal Prerequisite System (MPS)
    purpose: Constraint language that simultaneously encodes order-sensitive prerequisites and matroidal substitutability.
    Central modeling contribution; defined in Def. 4.1 and shown cryptomorphic to strong polymatroid greedoids.
  • Structural parameters Δ and λ_max
    purpose: Quantify distance of an MPS from a pure matroid and from a pure poset antimatroid, respectively, and control approximation ratios.
    Defined in Eqs. (1)–(2); appear in every guarantee and in the hardness statement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation Algorithms for Matroidal Prerequisite Systems." pith.science (2026). https://pith.science/paper/3BWDR2LC

@misc{pith2026260708151,
  author       = {Pith},
  title        = {Pith review of: Approximation Algorithms for Matroidal Prerequisite Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3BWDR2LC}},
  note         = {Machine review of arXiv:2607.08151}
}
abstract

Optimal selections in a decision process are often constrained by prerequisites. However, such prerequisites can encode functional rather than literal dependencies, so a required dependency may be supplied by one or several interacting alternatives. We introduce matroidal prerequisite systems (MPS), a constraint structure where a poset specifies prerequisites while a matroid determines when those prerequisites have been satisfied by its span. This creates an order-sensitive notion of feasibility over words, where feasible words are associated with independent sets, while dependencies may be fulfilled through substitutable functionality. Our main contribution is approximation algorithms for additive maximization and submodular maximization over the feasible words of an MPS. The guarantees are determined by two structural parameters: the maximum matroid rank $\Delta$ of a principal ideal in the poset and the maximum matroid connectivity $\lambda_\mathrm{max}$. These measure the distance an MPS is from encoding a matroid or a poset antimatroid, respectively, both of which are generalized by an MPS. For additive maximization, we obtain efficient deterministic $\Delta$- and $(1+\lambda_\mathrm{max})$-approximation algorithms. By extending these techniques, we obtain efficient deterministic $(2+\lambda_\mathrm{max})$-approximation and randomized $(\Delta^2\cdot(1 - 1/e - \delta)^{-1})$-approximation algorithms for all $\delta >0$ for submodular maximization. The algorithm design and analysis use the theory of polymatroid greedoids, via cryptomorphism we prove between an MPS and a strong polymatroid greedoid. Finally, an approximation-preserving reduction from densest $k$-subgraph shows it is not possible to efficiently compute a $\min\{\Delta,\lambda_\mathrm{max}\}^{o(1)}$-approximation to additive maximization over the feasible words of an MPS under the Gap Exponential Time Hypothesis.

Figures

Figures reproduced from arXiv: 2607.08151 by the authors.

Figure 1
Figure 1. Left shows a bridge. Following Example 4.4, the modal signatures of the baseline sensor of [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. The lattice of flats (Λ/∼, ⊑) and flat supports (κ(Λ/∼), ⊆) associated with the MPS from [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

132 extracted references · 132 canonical work pages

  1. [1]

    Machine Learning , volume=

    Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers , author=. Machine Learning , volume=. 1995 , publisher=

    work page 1995

  2. [2]

    Journal of Combinatorial Theory, Series B , volume=

    A combinatorial algorithm minimizing submodular functions in strongly polynomial time , author=. Journal of Combinatorial Theory, Series B , volume=. 2000 , publisher=

    work page 2000

  3. [3]

    Journal of the ACM (JACM) , volume=

    A combinatorial strongly polynomial algorithm for minimizing submodular functions , author=. Journal of the ACM (JACM) , volume=. 2001 , publisher=

    work page 2001

  4. [4]

    Mathematical Programming , volume=

    A faster strongly polynomial time algorithm for submodular function minimization , author=. Mathematical Programming , volume=. 2009 , publisher=

    work page 2009

  5. [5]

    Mathematical Programming The State of the Art: Bonn 1982 , pages=

    Submodular functions and convexity , author=. Mathematical Programming The State of the Art: Bonn 1982 , pages=. 1983 , publisher=

    work page 1982

  6. [6]

    SIAM Journal on Computing , pages=

    Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint , author=. SIAM Journal on Computing , pages=. 2025 , publisher=

    work page 2025

  7. [7]

    Submodular Function Maximization over Distributive and Integer Lattices

    Submodular function maximization over distributive and integer lattices , author=. arXiv preprint arXiv:1505.05423 , year=

    work page Pith review arXiv

  8. [8]

    Advances in Applied Mathematics , volume=

    Rank axiom of modular supermatroids: A connection with directional DR submodular functions , author=. Advances in Applied Mathematics , volume=. 2022 , publisher=

    work page 2022

Show all 132 references
  1. [9]

    SIAM Journal on Computing , volume=

    Monotone submodular maximization over a matroid via non-oblivious local search , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  2. [10]

    Mathematics of Operations Research , volume=

    Best algorithms for approximating the maximum of a submodular set function , author=. Mathematics of Operations Research , volume=. 1978 , publisher=

    1978

  3. [11]

    Mathematics of Operations Research , volume=

    Optimal approximation for submodular and supermodular optimization with bounded curvature , author=. Mathematics of Operations Research , volume=. 2017 , publisher=

    2017

  4. [12]

    Canadian Journal of Mathematics , volume=

    Connectivity in matroids , author=. Canadian Journal of Mathematics , volume=. 1966 , publisher=

    1966

  5. [13]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=

    Dependent randomized rounding via exchange properties of combinatorial structures , author=. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=. 2010 , organization=

    2010

  6. [14]

    Computer Methods in Applied Mechanics and Engineering , volume=

    Systematic sensor placement for structural anomaly detection in the absence of damaged states , author=. Computer Methods in Applied Mechanics and Engineering , volume=. 2020 , publisher=

    2020

  7. [15]

    , author=

    Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. , author=. Journal of Machine Learning Research , volume=

  8. [16]

    Electronic Notes in Discrete Mathematics , volume=

    Submodularity and randomized rounding techniques for optimal experimental design , author=. Electronic Notes in Discrete Mathematics , volume=. 2010 , publisher=

    2010

  9. [17]

    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Determinant maximization via matroid intersection algorithms , author=. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2022

  10. [18]

    International conference on machine learning , pages=

    Multi-fidelity black-box optimization with hierarchical partitions , author=. International conference on machine learning , pages=. 2018 , organization=

    2018

  11. [19]

    Hypergraph Seminar , pages=

    Aspects of the theory of hypermatroids , author=. Hypergraph Seminar , pages=. 1974 , organization=

    1974

  12. [20]

    SIAM Journal on Discrete Mathematics , volume=

    The natural matroid of an integer polymatroid , author=. SIAM Journal on Discrete Mathematics , volume=. 2023 , publisher=

    2023

  13. [21]

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

    Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  14. [22]

    Electronic colloquium on computational complexity ECCC; research reports, surveys and books in computational complexity , pages=

    Mildly exponential reduction from gap-3sat to polynomial-gap label-cover , author=. Electronic colloquium on computational complexity ECCC; research reports, surveys and books in computational complexity , pages=

  15. [23]

    44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=

    A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs , author=. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=. 2017 , organization=

    2017

  16. [24]

    Journal of Computer and System Sciences , volume=

    The complexity of parallel search , author=. Journal of Computer and System Sciences , volume=. 1988 , publisher=

    1988

  17. [25]

    Journal of Combinatorial Theory, Series B , volume=

    Matroid matching and some applications , author=. Journal of Combinatorial Theory, Series B , volume=. 1980 , publisher=

    1980

  18. [26]

    SIAM Journal on Computing , volume=

    Maximizing a monotone submodular function subject to a matroid constraint , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  19. [27]

    Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , pages=

    Balanced matroids , author=. Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , pages=

  20. [28]

    Discrete Mathematics & Theoretical Computer Science , author=

    Representing matroids over the reals is. Discrete Mathematics & Theoretical Computer Science , author=. 2024 , month=

    2024

  21. [29]

    Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Predicate detection to solve combinatorial optimization problems , author=. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

  22. [30]

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

    Max cut and the smallest eigenvalue , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

  23. [31]

    arXiv preprint arXiv:1008.3938 , year=

    Combinatorial approximation algorithms for maxcut using random walks , author=. arXiv preprint arXiv:1008.3938 , year=

    arXiv

  24. [32]

    Proceedings of the 23rd International Conference on Distributed Computing and Networking , pages=

    A lattice linear predicate parallel algorithm for the dynamic programming problems , author=. Proceedings of the 23rd International Conference on Distributed Computing and Networking , pages=

  25. [33]

    International Symposium on Stabilizing, Safety, and Security of Distributed Systems , pages=

    A lattice linear predicate parallel algorithm for the housing market problem , author=. International Symposium on Stabilizing, Safety, and Security of Distributed Systems , pages=. 2021 , organization=

    2021

  26. [34]

    2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages=

    Parallel minimum spanning tree algorithms via lattice linear predicate detection , author=. 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages=. 2022 , organization=

    2022

  27. [35]

    arXiv preprint arXiv:2512.18141 , year=

    Constrained Cuts, Flows, and Lattice-Linearity , author=. arXiv preprint arXiv:2512.18141 , year=

  28. [36]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  29. [37]

    Mathematics of Operations Research , volume=

    On knapsacks, partitions, and a new dynamic programming technique for trees , author=. Mathematics of Operations Research , volume=. 1983 , publisher=

    1983

  30. [38]

    Journal of optimization theory and applications , volume=

    Heuristic and exact algorithms for the precedence-constrained knapsack problem , author=. Journal of optimization theory and applications , volume=. 2000 , publisher=

    2000

  31. [39]

    Algorithmica , volume=

    Primal--dual algorithms for precedence constrained covering problems , author=. Algorithmica , volume=. 2017 , publisher=

    2017

  32. [40]

    Management science , volume=

    Maximal closure of a graph and applications to combinatorial problems , author=. Management science , volume=. 1976 , publisher=

    1976

  33. [41]

    Discrete Applied Mathematics , volume=

    Partially ordered knapsack and applications to scheduling , author=. Discrete Applied Mathematics , volume=. 2007 , publisher=

    2007

  34. [42]

    European Symposium on Algorithms , pages=

    Improved approximations for k-exchange systems , author=. European Symposium on Algorithms , pages=. 2011 , organization=

    2011

  35. [43]

    Mathematical Programming , volume=

    An analysis of approximations for maximizing submodular set functions—I , author=. Mathematical Programming , volume=. 1978 , publisher=

    1978

  36. [44]

    Mathematics of Operations Research , volume=

    Submodular maximization over multiple matroids via generalized exchange properties , author=. Mathematics of Operations Research , volume=. 2010 , publisher=

    2010

  37. [45]

    Annals of Discrete Mathematics , volume=

    An analysis of the greedy heuristic for independence systems , author=. Annals of Discrete Mathematics , volume=. 1978 , publisher=

    1978

  38. [46]

    European Symposium on Algorithms , pages=

    Greedy in approximation algorithms , author=. European Symposium on Algorithms , pages=. 2006 , organization=

    2006

  39. [47]

    arXiv preprint arXiv:2507.08194 , year=

    On the Parallel Complexity of Finding a Matroid Basis , author=. arXiv preprint arXiv:2507.08194 , year=

  40. [48]

    arXiv preprint arXiv:2511.04826 , year=

    Optimal Parallel Basis Finding in Graphic and Related Matroids , author=. arXiv preprint arXiv:2511.04826 , year=

  41. [49]

    Journal of the American Mathematical Society , volume=

    On the number of zero-patterns of a sequence of polynomials , author=. Journal of the American Mathematical Society , volume=

  42. [50]

    Journal of the ACM (JACM) , volume=

    Learnability and the Vapnik-Chervonenkis dimension , author=. Journal of the ACM (JACM) , volume=. 1989 , publisher=

    1989

  43. [51]

    2014 , publisher=

    Understanding machine learning: From theory to algorithms , author=. 2014 , publisher=

    2014

  44. [52]

    The Journal of Machine Learning Research , volume=

    The algebraic combinatorial approach for low-rank matrix completion , author=. The Journal of Machine Learning Research , volume=. 2015 , publisher=

    2015

  45. [53]

    arXiv preprint arXiv:2507.07220 , year=

    Linearizing algebraic matroids , author=. arXiv preprint arXiv:2507.07220 , year=

  46. [54]

    Journal of Combinatorial Theory, Series B , volume=

    Polymatroid greedoids , author=. Journal of Combinatorial Theory, Series B , volume=. 1985 , publisher=

    1985

  47. [55]

    Annals of discrete Mathematics , volume=

    Matroid intersection , author=. Annals of discrete Mathematics , volume=. 1979 , publisher=

    1979

  48. [56]

    Geometriae dedicata , volume=

    The theory of convex geometries , author=. Geometriae dedicata , volume=. 1985 , publisher=

    1985

  49. [57]

    2005 , publisher=

    Submodular functions and optimization , author=. 2005 , publisher=

    2005

  50. [58]

    Mathematical Programming , volume=

    Discrete convex analysis , author=. Mathematical Programming , volume=. 1998 , publisher=

    1998

  51. [59]

    Journal of Combinatorial Theory, Series B , volume=

    An intersection theorem for supermatroids , author=. Journal of Combinatorial Theory, Series B , volume=. 1990 , publisher=

    1990

  52. [60]

    Advances in Mathematics , volume=

    A cover-preserving embedding of semimodular lattices into geometric lattices , author=. Advances in Mathematics , volume=. 2010 , publisher=

    2010

  53. [61]

    Order , volume=

    A construction of semimodular lattices , author=. Order , volume=. 1985 , publisher=

    1985

  54. [62]

    Canadian Journal of Mathematics , volume=

    A semimodular imbedding of lattices , author=. Canadian Journal of Mathematics , volume=. 1960 , publisher=

    1960

  55. [63]

    1973 , publisher=

    Algebraic Theory of Lattices , author=. 1973 , publisher=

    1973

  56. [64]

    Discrete mathematics , volume=

    Cover preserving embedding of modular lattices into partition lattices , author=. Discrete mathematics , volume=. 1993 , publisher=

    1993

  57. [65]

    Discrete applied mathematics , volume=

    A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids , author=. Discrete applied mathematics , volume=. 1988 , publisher=

    1988

  58. [66]

    Order , volume=

    Polymatroids, closure operators and lattices , author=. Order , volume=. 2023 , publisher=

    2023

  59. [67]

    European Journal of Combinatorics , volume=

    A note on selectors and greedoids , author=. European Journal of Combinatorics , volume=. 1985 , publisher=

    1985

  60. [68]

    Discrete mathematics , volume=

    Greedoids and searches in directed graphs , author=. Discrete mathematics , volume=. 1991 , publisher=

    1991

  61. [69]

    Discrete Mathematics , volume=

    The intersection of matroids and antimatroids , author=. Discrete Mathematics , volume=. 1988 , publisher=

    1988

  62. [70]

    Discrete mathematics , volume=

    Exchange systems , author=. Discrete mathematics , volume=. 1988 , publisher=

    1988

  63. [71]

    Proceedings of the third international conference on Combinatorial mathematics , pages=

    Polyhedral results for antimatroids , author=. Proceedings of the third international conference on Combinatorial mathematics , pages=

  64. [72]

    Discrete Applied Mathematics , volume=

    Violator spaces: structure and algorithms , author=. Discrete Applied Mathematics , volume=. 2008 , publisher=

    2008

  65. [73]

    Axioms , volume=

    Greedoids and Violator Spaces , author=. Axioms , volume=. 2024 , publisher=

    2024

  66. [74]

    Building Bridges: Between Mathematics and Computer Science , pages=

    Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries , author=. Building Bridges: Between Mathematics and Computer Science , pages=. 2008 , publisher=

    2008

  67. [75]

    European Journal of Combinatorics , volume=

    Chip-firing games on graphs , author=. European Journal of Combinatorics , volume=. 1991 , publisher=

    1991

  68. [76]

    Proceedings of the ninth annual symposium on Computational geometry , pages=

    Helly theorems and generalized linear programming , author=. Proceedings of the ninth annual symposium on Computational geometry , pages=

  69. [77]

    1998 , publisher=

    Theory of linear and integer programming , author=. 1998 , publisher=

    1998

  70. [78]

    American Journal of Mathematics , volume=

    Abstract linear dependence and lattices , author=. American Journal of Mathematics , volume=. 1935 , publisher=

    1935

  71. [79]

    Combinatorial Optimization—Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5--9, 2001 Revised Papers , pages=

    Submodular functions, matroids, and certain polyhedra , author=. Combinatorial Optimization—Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5--9, 2001 Revised Papers , pages=. 2003 , organization=

    2001

  72. [80]

    2003 , publisher=

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

    2003

  73. [81]

    2012 , publisher=

    Greedoids , author=. 2012 , publisher=

    2012

  74. [82]

    Journal of Combinatorial Theory, Series B , volume=

    Geometries on partially ordered sets , author=. Journal of Combinatorial Theory, Series B , volume=. 1980 , publisher=

    1980

  75. [83]

    Journal of the ACM (JACM) , volume=

    On ordered languages and the optimization of linear functions by greedy algorithms , author=. Journal of the ACM (JACM) , volume=. 1985 , publisher=

    1985

  76. [84]

    , author=

    The greedy algorithm for partially ordered sets. , author=. Discret. Math. , volume=

  77. [85]

    Mathematical Programming , volume=

    New polyhedral and algorithmic results on greedoids , author=. Mathematical Programming , volume=. 2021 , publisher=

    2021

  78. [86]

    Journal of Combinatorial Optimization , volume=

    Sufficient conditions for the optimality of the greedy algorithm in greedoids , author=. Journal of Combinatorial Optimization , volume=. 2022 , publisher=

    2022

  79. [87]

    SIAM Journal on Algebraic Discrete Methods , volume=

    Greedoids and linear objective functions , author=. SIAM Journal on Algebraic Discrete Methods , volume=. 1984 , publisher=

    1984

  80. [88]

    Constraints , volume=

    Formal languages for integer programming modeling of shift scheduling problems , author=. Constraints , volume=. 2011 , publisher=

    2011

  81. [89]

    Matroid applications , volume=

    Introduction to greedoids , author=. Matroid applications , volume=. 1992 , publisher=

    1992

  82. [90]

    Mathematical Programming , volume=

    Matroids and the greedy algorithm , author=. Mathematical Programming , volume=. 1971 , publisher=

    1971

  83. [91]

    Proceedings of the London Mathematical Society , volume=

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

    1957

  84. [92]

    Progress in combinatorial optimization , pages=

    Greedoids-A structural framework for the greedy algorithm , author=. Progress in combinatorial optimization , pages=. 1984 , publisher=

    1984

  85. [93]

    Discrete Mathematics , volume=

    Non-interval greedoids and the transposition property , author=. Discrete Mathematics , volume=. 1986 , publisher=

    1986

  86. [94]

    Journal of Combinatorial Theory, Series B , volume=

    A characterization of undirected branching greedoids , author=. Journal of Combinatorial Theory, Series B , volume=. 1988 , publisher=

    1988

  87. [95]

    1986 , publisher=

    Theory of matroids , author=. 1986 , publisher=

    1986

  88. [96]

    2006 , publisher=

    Matroid theory , author=. 2006 , publisher=

    2006

  89. [97]

    2010 , publisher=

    Matroid theory , author=. 2010 , publisher=

    2010

  90. [98]

    2012 , publisher=

    Finite ordered sets: concepts, results and uses , author=. 2012 , publisher=

    2012

  91. [99]

    2011 , publisher=

    Lattice theory: foundation , author=. 2011 , publisher=

    2011

  92. [100]

    2002 , publisher=

    Introduction to lattices and order , author=. 2002 , publisher=

    2002

  93. [101]

    Algebra Universalis , volume=

    Modular elements of geometric lattices , author=. Algebra Universalis , volume=. 1971 , publisher=

    1971

  94. [102]

    Cambridge studies in advanced mathematics , year=

    Enumerative Combinatorics Volume 1 second edition , author=. Cambridge studies in advanced mathematics , year=

  95. [103]

    2015 , publisher=

    Introduction to lattice theory with computer science applications , author=. 2015 , publisher=

    2015

  96. [104]

    Discrete & Computational Geometry , volume=

    Convexity and the beta invariant , author=. Discrete & Computational Geometry , volume=. 1999 , publisher=

    1999

  97. [105]

    Advances in Applied Mathematics , volume=

    Homotopy properties of greedoids , author=. Advances in Applied Mathematics , volume=. 1985 , publisher=

    1985

  98. [106]

    Advances in Mathematics , volume=

    Selectors: a theory of formal languages, semimodular lattices, and branching and shelling processes , author=. Advances in Mathematics , volume=. 1984 , publisher=

    1984

  99. [107]

    Mathematical Programming , volume=

    Structures of polyhedra determined by submodular functions on crossing families , author=. Mathematical Programming , volume=. 1984 , publisher=

    1984

  100. [108]

    Discussiones Mathematicae: General Algebra & Applications , volume=

    Revisiting Faigle geometries from a perspective of semimodular lattices , author=. Discussiones Mathematicae: General Algebra & Applications , volume=

  101. [109]

    SIAM Journal on Discrete Mathematics , volume=

    An exact characterization of greedy structures , author=. SIAM Journal on Discrete Mathematics , volume=. 1993 , publisher=

    1993

  102. [110]

    Discrete applied mathematics , volume=

    Linear objective functions on certain classes of greedoids , author=. Discrete applied mathematics , volume=. 1986 , publisher=

    1986

  103. [111]

    Mathematical Programming , volume=

    Minimizing symmetric submodular functions , author=. Mathematical Programming , volume=. 1998 , publisher=

    1998

  104. [112]

    Operations Research , volume=

    Computational complexity of some maximum average weight problems with precedence constraints , author=. Operations Research , volume=. 1994 , publisher=

    1994

  105. [113]

    SIAM Journal on Discrete Mathematics , volume=

    Matroidal choice functions , author=. SIAM Journal on Discrete Mathematics , volume=. 2019 , publisher=

    2019

  106. [114]

    Theoretical Economics , volume=

    Gross substitutes and endowed assignment valuations , author=. Theoretical Economics , volume=. 2015 , publisher=

    2015

  107. [115]

    Econometrica: Journal of the Econometric Society , pages=

    Job matching, coalition formation, and gross substitutes , author=. Econometrica: Journal of the Econometric Society , pages=. 1982 , publisher=

    1982

  108. [116]

    IET Radar, Sonar & Navigation , volume=

    Constrained robust submodular sensor selection with application to multistatic sonar arrays , author=. IET Radar, Sonar & Navigation , volume=. 2017 , publisher=

    2017

  109. [117]

    Theoretical Computer Science , volume=

    Sensor networks: From dependence analysis via matroid bases to online synthesis , author=. Theoretical Computer Science , volume=. 2014 , publisher=

    2014

  110. [118]

    Entropy , volume=

    Entropic matroids and their representation , author=. Entropy , volume=. 2019 , publisher=

    2019

  111. [119]

    Theoretical computer science , volume=

    Efficient algorithms for robustness in resource allocation and scheduling problems , author=. Theoretical computer science , volume=. 2006 , publisher=

    2006

  112. [120]

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

    Santa claus meets makespan and matroids: Algorithms and reductions , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  113. [121]

    Ruys, Pieter H. M. A General Equilibrium of Managed Services. Equilibrium, Markets and Dynamics: Essays in Honour of Claus Weddepohl. 2002

    2002

  114. [122]

    2019 IEEE 58th Conference on Decision and Control (CDC) , pages=

    Matroid-constrained approximately supermodular optimization for near-optimal actuator scheduling , author=. 2019 IEEE 58th Conference on Decision and Control (CDC) , pages=. 2019 , organization=

    2019

  115. [123]

    and Leiserson, Charles E

    Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , year=. Introduction to Algorithms , edition=

  116. [124]

    Annals of discrete mathematics , volume=

    Optimization and approximation in deterministic sequencing and scheduling: a survey , author=. Annals of discrete mathematics , volume=. 1979 , publisher=

    1979

  117. [125]

    Scheduling with AND/OR Precedence Constraints , journal =

    M\". Scheduling with AND/OR Precedence Constraints , journal =

  118. [126]

    Journal of Computer and System sciences , volume=

    NP-complete scheduling problems , author=. Journal of Computer and System sciences , volume=. 1975 , publisher=

    1975

  119. [127]

    Discrete Applied Mathematics , volume=

    An algorithmic characterization of antimatroids , author=. Discrete Applied Mathematics , volume=. 1990 , publisher=

    1990

  120. [128]

    The Journal of Machine Learning Research , volume=

    Proximal methods for hierarchical sparse coding , author=. The Journal of Machine Learning Research , volume=. 2011 , publisher=

    2011

  121. [129]

    Foundations and Trends

    Optimization with sparsity-inducing penalties , author=. Foundations and Trends. 2012 , publisher=

    2012

  122. [130]

    2015 International Conference on Distributed Computing in Sensor Systems , pages=

    On exploiting logical dependencies for minimizing additive cost metrics in resource-limited crowdsensing , author=. 2015 International Conference on Distributed Computing in Sensor Systems , pages=. 2015 , organization=

    2015

  123. [131]

    IEEE Transactions on Signal Processing , volume=

    Subspace selection for projection maximization with matroid constraints , author=. IEEE Transactions on Signal Processing , volume=. 2016 , publisher=

    2016

  124. [132]

    arXiv preprint arXiv:2411.15363 , year=

    The Polymatroid Representation of a Greedoid, and Associated Galois Connections , author=. arXiv preprint arXiv:2411.15363 , year=

    arXiv

Pith tools

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