Submodular Maximization Over Ordered Sequences

55 concepts36 papers1 proposal

In classical combinatorial optimization, submodularity formalizes the intuitive notion of "diminishing returns." Imagine choosing a set of features for a machine learning model or a set of sensors to monitor a network. The law of diminishing returns dictates that adding a specific sensor to a small initial deployment provides a much larger marginal benefit than adding that same sensor to a massive, already comprehensive network.

Mathematically, for an unordered set function $f$, this is expressed as:

$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B) \quad \text{whenever } A \subseteq B$$

This elegant property makes large-scale optimization tractable. A simple greedy algorithm—iteratively picking the element with the highest marginal gain—is guaranteed to capture at least $(1 - 1/e) \approx 63\%$ of the optimal solution's value.

However, this classical framework relies on a critical assumption: order does not matter. The utility of a set depends solely on its composition, not on the sequence in which its elements are arranged or consumed.

In many real-world applications, this assumption fails completely:

  • User Interfaces & Search Feeds: In e-commerce or search engines, users read from top to bottom. An excellent recommendation placed at position 20 might never be seen if the user loses patience and leaves at position 5.
  • Dependent Content Consumption: In education or entertainment, the utility of a course or a movie sequel depends strictly on what came before it. Taking Advanced Calculus before Linear Algebra yields a completely different utility than taking them in the logical order.
  • Physical Trajectories: In robotic path planning or sensor scheduling, the physical sequence of actions dictates the cost and feasibility of the entire operation.

To address these scenarios, a growing body of research has extended submodularity from unordered sets to ordered sequences, creating a framework known as sequential submodular optimization.


Why Order Breaks Standard Submodularity

When we move from sets to sequences, the mathematical symmetry of exchangeability vanishes. If we treat a sequence as a string $\sigma$, the marginal utility of adding an item $x$ is no longer determined by a surrounding subset, but by its exact position and its prefix—the specific sequence of items that preceded it.

As Liang Feng 0001 et al. observe in their work on Budgeted Sequence Submodular Maximization, some utility functions exhibit submodular properties only when items are arranged in specific sequences. If we ignore this order, the mathematical guarantees of standard submodular optimization collapse.

To restore these guarantees, researchers have developed three primary ways to model order-dependent utility:

1. Prefix Dependency

In this formulation, the utility of an element is strictly a function of the element itself and the ordered sequence of elements that came before it. Jing Yuan 0002 et al. leverage this in Learning Submodular Sequencing from Samples to optimize rankings where an item's value changes dynamically based on its position and historical context.

2. Directed Graphs and Active Edges

Instead of evaluating items individually, we can model sequential dependencies as a Directed Acyclic Graph (DAG). Sebastian Tschiatschek et al. introduced this perspective in Selecting Sequences of Items via Submodular Maximization. Here, utility is defined as a submodular function over a set of active edges—edges where the source node appears anywhere before the destination node in the sequence. This elegantly captures diminishing returns across chains of events (e.g., category fatigue in movie recommendations) while preserving strong approximation guarantees.

Unordered Set:     { A, B, C }  --> Utility is static
Ordered Sequence:  A -> B -> C  --> Active Edges: (A,B), (A,C), (B,C)

3. Hidden Submodular Order

Sometimes, a function appears completely non-submodular (subadditive) across arbitrary sets, but possesses a hidden structural order. In Submodular Order Functions and Assortment Optimization, Rajan Udwani demonstrates that if elements are processed in a specific sequence—such as descending order of retail price—the diminishing returns property is restored. This structural insight allows algorithms to manage complex substitution effects in retail assortment that would otherwise be computationally intractable.


The Mechanics of Sequential Guarantees: Curvature

If the marginal gain of an action depends on its direction and history, how can we prove that a greedy strategy will find a good sequence?

In set optimization, the performance of greedy algorithms is often bounded by the curvature of the function, which measures how close the function is to being purely linear. For sequences, this concept must become directional. Zhenliang Zhang 0001 et al. resolved this in Near optimality of greedy strategies for string submodular functions with forward and backward curvature constraints by splitting curvature into two distinct constraints:

  • Forward Curvature: Measures how much a sequence of past actions blunts the effectiveness of a future action.
  • Backward Curvature: Measures how much future actions influence or diminish the value of early choices.

By distinguishing between these forward and backward influences on string functions, the authors extended classical matroid theory to sequences via string-matroid constraints. This mathematical framework defines feasible sets of strings, proving that if a sequential function exhibits properties like postfix monotonicity (where adding elements to the end of a sequence never reduces total utility), a greedy strategy remains remarkably close to the theoretical optimum.


Real-World Applications: Cascades, Bandits, and Solvers

The transition from sets to sequences has fundamentally changed how we design interactive systems, online learning algorithms, and discrete optimization pipelines.

User Cascades and Position Bias

In web applications, user engagement is a sequential process. Shaojie Tang 0001 et al. formalize this in Adaptive Cascade Submodular Maximization, modeling scenarios where a user scans a list of items sequentially and may stop at any moment. The total utility depends on the sequence and the probability that the user remains engaged long enough to encounter subsequent items.

Similarly, Gaurush Hiranandani et al. developed the Cascading Linear Submodular Bandits framework to balance position bias with content diversity. By greedily selecting items that maximize marginal utility at each successive rank, their approach handles complex online ranking tasks where user attention decays rapidly down the page.

Position 1: [ High Utility Item ]  --> User Clicks or Continues
Position 2: [ Diverse Alternative ] --> Decreases redundancy given Pos 1
Position 3: [ Niche Content ]       --> Lower probability of being reached

Marketing Fatigue and Abandonment

Sequence optimization can also prevent negative user experiences. In Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue, Junyu Cao and Wei Sun study how over-messaging causes users to abandon platforms entirely. They show that the optimal sequence can be found by calculating a normalized expected payoff score for each item and sorting them in descending order, reducing a complex combinatorial search into a fast, linear sorting task.

Accelerating Discrete Solvers

Beyond user-facing applications, sequence-aware modeling is transforming discrete optimization itself. In Mixed-Integer Linear Programming (MILP), solvers rely on adding "cutting planes" to prune search spaces.

In Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model, Zhihai Wang et al. demonstrate that the order in which these cuts are applied drastically impacts solver efficiency. By treating cut selection as a sequence generation problem rather than an unordered subset selection problem, their model accounts for the mutual interactions and redundancies between successive cuts, significantly outperforming traditional human-designed heuristics.


Summary

Sequential submodular optimization bridges the gap between the mathematical tractability of diminishing returns and the path-dependent reality of the physical and digital worlds. By redefining utility over prefixes, active edges, and directional curvatures, this framework allows greedy algorithms to navigate exponential permutation spaces with provable, near-optimal performance guarantees.

Key Foundational Work

Non-Stochastic Bandit Slate Problems (2010) — contributed 1 concept elements to this direction.
Randomized Decoding for Selection-and-Ordering Problems (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_submodular_optimization_bfe996b1,
  title = {sequential submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-submodular-optimization/rdr_bfe996b1ce9a4e408f59e0d1abd74f5f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_submodular_optimization_bfe996b1_v1,
  title = {sequential submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-submodular-optimization/rdr_bfe996b1ce9a4e408f59e0d1abd74f5f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake