pith. sign in

arxiv: 1907.04279 · v1 · pith:3MHS4GDWnew · submitted 2019-07-09 · 💻 cs.DS

Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---

Takanori Maehara , So Nakashima , Yutaro Yamaguchi This is my paper

Pith reviewed 2026-05-25 00:00 UTC · model grok-4.3

classification 💻 cs.DS
keywords DR-submodular maximizationdistributive latticecontinuous greedy algorithmmedian complexknapsack constraintsmultilinear extensionapproximation algorithm
0
0 comments X

The pith

A 1-1/e approximation algorithm exists for monotone DR-submodular maximization under multiple order-consistent knapsack constraints on distributive lattices.

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

The paper establishes a 1-1/e approximation for maximizing a monotone DR-submodular function subject to several knapsack constraints that respect the partial order of a distributive lattice. This setting captures dependency-constrained submodular problems on sets. The algorithm generalizes the continuous greedy method by relaxing the lattice to its median complex and defining a multilinear extension there. The key step shows that uniform linear motions on this complex make the extension concave for DR-submodular functions, allowing the standard greedy analysis to carry over.

Core claim

We propose a 1-1/e approximation algorithm for monotone DR-submodular maximization under multiple order-consistent knapsack constraints on a distributive lattice. The algorithm works by choosing the median complex as a continuous relaxation of the lattice, defining the multilinear extension of the objective on this complex, and showing that uniform linear motions exist along which the extension is concave; this concavity enables the continuous greedy procedure to achieve the stated guarantee.

What carries the argument

The median complex of the distributive lattice, equipped with uniform linear motions along which the multilinear extension of any DR-submodular function is concave.

If this is right

  • The same continuous-greedy procedure applies to any distributive-lattice formulation of dependency-constrained submodular maximization.
  • The 1-1/e guarantee holds for any number of order-consistent knapsack constraints.
  • The median-complex relaxation can replace the standard continuous relaxation when the ground set carries a lattice structure.
  • Uniform linear motions supply a concrete path for integrating the continuous greedy vector field on the lattice.

Where Pith is reading between the lines

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

  • The technique may extend to other poset relaxations that admit concave directions for multilinear extensions.
  • Order-consistent knapsack constraints could model precedence relations in scheduling or feature-selection tasks with dependencies.
  • If uniform linear motions can be computed efficiently, the algorithm becomes practical for moderate-sized lattices arising from dependency graphs.

Load-bearing premise

The median complex of any distributive lattice contains uniform linear motions that render the multilinear extension concave for every monotone DR-submodular function.

What would settle it

An explicit distributive lattice, monotone DR-submodular function, and set of order-consistent knapsack constraints for which no uniform linear motion yields concavity of the multilinear extension, or for which the resulting algorithm returns a solution worse than 1-1/e of optimal.

Figures

Figures reproduced from arXiv: 1907.04279 by So Nakashima, Takanori Maehara, Yutaro Yamaguchi.

Figure 3.1
Figure 3.1. Figure 3.1: The median complex and uniform linear motion fro [PITH_FULL_IMAGE:figures/full_fig_p008_3_1.png] view at source ↗
read the original abstract

We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a $1 - 1/e$ approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of a distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions, such that the multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property of the continuous greedy algorithm.

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

1 major / 1 minor

Summary. The paper claims a 1-1/e approximation algorithm for maximizing a monotone DR-submodular function subject to multiple order-consistent knapsack constraints on a distributive lattice. It achieves this by generalizing the continuous greedy algorithm: the median complex serves as the continuous relaxation of the lattice, the multilinear extension is defined on it, and the key structural fact is that this extension is concave along positive uniform linear motions, allowing the standard continuous-greedy analysis to carry over.

Significance. If the concavity property is established, the result meaningfully extends continuous-greedy techniques from the boolean lattice to distributive lattices with dependency constraints, providing a new algorithmic handle on a natural generalization of submodular maximization. The introduction of the median complex and uniform linear motions as geometric objects is a concrete contribution that could be reused in other lattice optimization settings.

major comments (1)
  1. The concavity of the multilinear extension along positive uniform linear motions on the median complex is the single load-bearing step for transferring the continuous-greedy analysis and obtaining the 1-1/e guarantee. The abstract states this property but supplies no derivation; the manuscript must contain an explicit proof (ideally computing the second derivative along such a motion and showing it is non-positive for every monotone DR-submodular function) that does not rely on additional unstated assumptions about the geometry of the median complex.
minor comments (1)
  1. The abstract uses the phrase 'order-consistent knapsack constraints' without a forward reference to its formal definition; a one-sentence clarification or pointer to the relevant section would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and for identifying the need for an explicit proof of the key concavity property. We agree that this step is central to the 1-1/e guarantee and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: The concavity of the multilinear extension along positive uniform linear motions on the median complex is the single load-bearing step for transferring the continuous-greedy analysis and obtaining the 1-1/e guarantee. The abstract states this property but supplies no derivation; the manuscript must contain an explicit proof (ideally computing the second derivative along such a motion and showing it is non-positive for every monotone DR-submodular function) that does not rely on additional unstated assumptions about the geometry of the median complex.

    Authors: We agree that an explicit derivation is required. The current manuscript states the concavity result but does not include the second-derivative calculation. In the revision we will insert a self-contained proof that directly computes the second derivative of the multilinear extension along any positive uniform linear motion on the median complex and shows it is non-positive whenever the underlying function is monotone and DR-submodular. The argument will use only the definition of DR-submodularity on the lattice and the coordinate-wise structure of the median complex; no additional geometric assumptions will be invoked. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation introduces independent geometric property of median complex to enable continuous greedy

full rationale

The paper defines the median complex as a continuous relaxation of a distributive lattice, defines the multilinear extension on it, and proves that this extension is concave along uniform linear motions for monotone DR-submodular functions. This concavity is presented as a newly shown structural fact that transfers the continuous-greedy analysis to obtain the 1-1/e guarantee under the knapsack constraints. No step reduces a claimed prediction or result to a fitted parameter, self-definition, or self-citation chain by construction; the load-bearing concavity is an independent proof rather than an ansatz or renaming. The approach generalizes known continuous-greedy techniques without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The paper relies on domain assumptions about DR-submodularity and order-consistency of constraints while introducing new geometric constructs (median complex, uniform linear motions) whose properties are established within the derivation without external independent evidence.

axioms (2)
  • domain assumption Distributive lattices can represent dependency constraints in optimization problems.
    Invoked in the abstract as the motivation for modeling the problem on distributive lattices.
  • ad hoc to paper Monotone DR-submodular functions admit a multilinear extension that is concave along positive uniform linear motions on the median complex.
    This is presented as the key property shown to enable the continuous greedy algorithm.
invented entities (2)
  • median complex no independent evidence
    purpose: Continuous relaxation of a distributive lattice for defining the multilinear extension
    Newly introduced as the space on which the extension and concavity are defined.
  • uniform linear motion no independent evidence
    purpose: Special curves on the median complex along which concavity of the multilinear extension holds
    Newly defined to support the concavity property required for the algorithm.

pith-pipeline@v0.9.0 · 5679 in / 1658 out tokens · 39171 ms · 2026-05-25T00:00:36.898818+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

27 extracted references · 27 canonical work pages · 2 internal anchors

  1. [1]

    Pipage roundin g: A new method of constructing algorithms with proven performance guarantee

    Alexander A Ageev and Maxim I Sviridenko. Pipage roundin g: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization , 8(3):307–328, 2004

    work page 2004

  2. [2]

    Optimizi ng budget allocation among channels and influencers

    Noga Alon, Iftah Gamzu, and Moshe Tennenholtz. Optimizi ng budget allocation among channels and influencers. In Proceedings of the 21st international conference on World Wid e Web , pages 381–388. ACM, 2012

    work page 2012

  3. [3]

    Metric graph the ory and geometry: a survey

    Hans-Jurgen Bandelt and Victor Chepoi. Metric graph the ory and geometry: a survey. Contemporary Mathematics, 453:49–86, 2008

    work page 2008

  4. [4]

    Braids, posets and orthosch emes

    Tom Brady and Jon McCammond. Braids, posets and orthosch emes. Algebraic & Geometric Topology , 10(4):2277–2314, 2010

    work page 2010

  5. [5]

    Metric spaces of non-positive curvature

    Martin R Bridson and André Haefliger. Metric spaces of non-positive curvature . Springer-Verlag, Berlin, 1999

    work page 1999

  6. [6]

    Maximizing a monotone submodular function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vo ndrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing , 40(6):1740–1766, 2011

    work page 2011

  7. [7]

    Weakly modular graphs and nonpositive curvature

    Jérémie Chalopin, Victor Chepoi, Hiroshi Hirai, and Dam ian Osajda. Weakly modular graphs and nonpositive curvature. arXiv e-prints , page arXiv:1409.3892, Sep 2014

    work page arXiv 2014

  8. [8]

    Submo dular function maximization via the multilinear relaxation and contention resolution schemes

    Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submo dular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing , 43(6):1831–1879, 2014

    work page 2014

  9. [9]

    Graphs of some cat(0) complexes

    Victor Chepoi. Graphs of some cat(0) complexes. Advances in Applied Mathematics , 24(2):125 – 179, 2000

    work page 2000

  10. [10]

    Location of ban k accounts of optimize float: An analytic study of exact and approximate algorithm

    G Cornnejols, M Fisher, and G Nemhauser. Location of ban k accounts of optimize float: An analytic study of exact and approximate algorithm. Management Science, 23:789–810, 1977

    work page 1977

  11. [11]

    A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

    Alina Ene and Huy L Nguyen. A reduction for optimizing la ttice submodular functions with diminishing returns. arXiv preprint arXiv:1606.08362 , 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  12. [12]

    A note on submod ular functions on distributive lattices

    Satoru Fujishige and Nobuaki Tomizawa. A note on submod ular functions on distributive lattices. Journal of the Operations Research Society of Japan , 26(4):309–318, 1983. 21

    work page 1983

  13. [13]

    Submodular Function Maximization over Distributive and Integer Lattices

    Corinna Gottschalk and Britta Peis. Submodular functi on maximization over distributive and integer lattices. arXiv preprint arXiv:1505.05423 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  14. [14]

    General lattice theory

    George Grätzer. General lattice theory . Springer Science & Business Media, 2002

    work page 2002

  15. [15]

    Gradient methods for submodular maximization

    Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi . Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems (NeurIPS’17 ), pages 5841–5851, 2017

    work page 2017

  16. [16]

    L-convexity on graph structures

    Hiroshi Hirai. L-convexity on graph structures. Journal of the Operations Research Society of Japan , 61(1):71–109, 2018

    work page 2018

  17. [17]

    Submodular functio n maximization

    Andreas Krause and Daniel Golovin. Submodular functio n maximization. In Tractability: Practical Approaches to Hard Problems , pages 71–104. Cambridge University Press, 2014

    work page 2014

  18. [18]

    Maximizin g submodular set functions subject to multiple linear constraints

    Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizin g submodular set functions subject to multiple linear constraints. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Di screte Algorithms (SODA’09), pages 545–554, 2009

    work page 2009

  19. [19]

    Submodular functions and convexity

    László Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art , pages 235–257. Springer, 1983

    work page 1983

  20. [20]

    Discrete convex analysis: A tool for economics and game theory

    Kazuo Murota et al. Discrete convex analysis: A tool for economics and game theory. Journal of Mechanism and Institution Design , 1(1):151–273, 2016

    work page 2016

  21. [21]

    Subspace selection via dr-submodular maximization on lattices

    So Nakashima and Takanori Maehara. Subspace selection via dr-submodular maximization on lattices. In Proceedings of the 33rd AAAI Conference on Artificial Intellig ence (AAAI’19), Honolulu, Hawaii, USA, January 27 - February 1, 2019 , 2019

    work page 2019

  22. [22]

    An analysis of approximations for maximizing submodular set functions – I

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fi sher. An analysis of approximations for maximizing submodular set functions – I. Mathematical Programming, 14(1):265–294, 1978

    work page 1978

  23. [23]

    Poc sets, median algebras and group acti ons, an extended study of dunwoody’s construction and sageev’ theorem

    Martin Roller. Poc sets, median algebras and group acti ons, an extended study of dunwoody’s construction and sageev’ theorem. Technical report, University of South ampton, 1998

    work page 1998

  24. [24]

    Maximizing monotone su bmodular functions over the integer lattice

    Tasuku Soma and Yuichi Yoshida. Maximizing monotone su bmodular functions over the integer lattice. Mathematical Programming, 172(1-2):539–563, 2018

    work page 2018

  25. [25]

    A note on maximizing a submodular set function subject to a knapsack constraint

    Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004

    work page 2004

  26. [26]

    Minimizing a submodular function on a l attice

    Donald M Topkis. Minimizing a submodular function on a l attice. Operations Research, 26(2):305–321, 1978

    work page 1978

  27. [27]

    Optimal approximation for the submodular welfare problem in the value oracle model

    Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th Annual ACM Symposium on Theory of Comp uting (STOC’08) , pages 67–74. ACM, 2008. 22

    work page 2008