Optimization often involves making the best choices under pressure. In computer science, a "sweet spot" for optimization is submodular maximization. If you’ve ever tried to pick the best set of sensors to cover a room or the most influential people on a social network, you’ve dealt with submodularity—the principle of diminishing returns.
While algorithms for solving these problems on simple sets are well-established, real-world constraints are often more complex. What if you cannot pick "Item B" unless you’ve already picked "Item A"? A recent paper by researchers from RIKEN, Tokyo, and Osaka provides a powerful new toolkit for solving these "dependency-constrained" problems with near-optimal efficiency.
Abstract
We consider the problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice can represent dependency constraints, this problem generalizes submodular maximization on sets to include dependencies. We propose a $1 - 1/e$ approximation algorithm by generalizing the continuous greedy algorithm to distributive lattices. This is achieved by using a median complex as a continuous relaxation and defining a multilinear extension on it. We demonstrate that the median complex admits "uniform linear motions" along which the multilinear extension is concave, a key property for the continuous greedy approach.
The Challenge of Dependencies
Standard submodular optimization usually occurs on a power set (choosing a subset from a collection). However, many real-world problems have dependency constraints. For example, in a manufacturing pipeline, Step 5 cannot be performed without completing Step 2. These dependencies are mathematically represented as a distributive lattice.
The authors focus on DR-submodular functions on these lattices. "DR" stands for Diminishing Returns, a stronger version of submodularity that is particularly useful when dealing with integer or lattice-based coordinates. The specific challenge addressed is adding multiple knapsack constraints (e.g., limited budget, time, and manpower) to this lattice structure while maintaining the gold-standard approximation ratio of $1 - 1/e$.
A Geometric Solution: The Median Complex
To solve this, the researchers moved the problem from a discrete, "jumpy" lattice into a smooth, continuous space to utilize calculus-based tools. Their approach involves mapping the discrete lattice onto a geometric structure called a median complex.
As shown in the figure above, the median complex can be thought of as a collection of high-dimensional cubes (hypercubes) glued together along their faces in a way that mirrors the lattice's dependencies. By defining a multilinear extension of the objective function across this complex, the algorithm can "walk" through the space smoothly rather than jumping between discrete points.
Key Innovations: Uniform Linear Motion
A technical breakthrough in this work is the introduction of Uniform Linear Motion (ULM). In a standard cube, moving in a straight line is straightforward. In a median complex where cubes are glued together, defining a "straight" path is more difficult. The authors introduced ULMs—paths that satisfy a "flow conservation law" at the boundaries where cubes meet. They proved that the objective function is concave along these paths, which is exactly what a greedy algorithm needs to find a global optimum efficiently.
Key Results and Theoretical Guarantees
- The $1-1/e$ Guarantee: The authors proved that their algorithm achieves a $(1 - \epsilon)(1 - 1/e)$ approximation ratio. This is significant because $1-1/e$ (roughly 63%) is the theoretical limit for how well any polynomial-time algorithm can solve these types of problems.
- Polynomial Time: Despite the geometric complexity, the algorithm is guaranteed to run in polynomial time relative to the size of the ground set, provided the number of knapsack constraints is small and fixed.
- Uniqueness of Motion: They proved that for any two points in the median complex, there is a unique ULM connecting them, providing a solid foundation for future geometric optimization research.
Limitations and Future Work
While the algorithm is polynomial time, it relies on partial enumeration, which can be computationally expensive in practice if the error tolerance ($\epsilon$) is very low. Additionally, the current proof only works for monotone functions; solving the non-monotone case on a median complex remains an open challenge. Finally, the algorithm assumes the number of knapsack constraints is small; if the number of constraints scales with the problem size, the complexity becomes significantly more daunting.
Summary updated