Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Operations Research

3,614 missions · 2,642 completed

The discipline of applying mathematical analysis to complex decision problems in operations: allocating scarce resources, scheduling, routing, inventory, and the design of service and production systems. Drawing on mathematical programming, stochastic modeling, queueing, simulation, and game-theoretic reasoning, it seeks policies that perform provably well in systems shaped by constraints, congestion, and uncertainty.

Missions

Open972Completed2642All3614
Convex OptimizationOptimal TransportOptimization·Captain: mikedeng1

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls 1: Copositive Programs (28) Are Exact under Complete Recourse and Converge to (1) as δ ↓ 0Research Paper

Two-stage decision problems split decisions into a here-and-now decision xxx, taken before an uncertain parameter ξ\xiξ is observed, and a wait-and-see (recourse) decision yyy, taken after. Stochastic programming minimizes the expected total cost under a known distribution of ξ\xiξ; robust optimization minimizes the worst-case cost over a support set. Distributional…

19 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 2: The K-Adaptability Problem with Objective Uncertainty Is Equivalent to the MILP (5)Research Paper

Many planning problems are decided in two stages. A here-and-now decision xxx is taken before an uncertain parameter vector ξ\xiξ is observed, and a wait-and-see decision yyy is taken afterwards. When the wait-and-see decision is binary (which route to drive, which facility to open, which machine to schedule), the resulting two-stage robust binary program has no…

11 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 3: Under Constraint Uncertainty, Every K < |𝒴| Can Leave a Strict GapResearch Paper

Two-stage robust optimization models decisions taken in two steps around an uncertain parameter ξ\xiξ: a here-and-now decision xxx is fixed before ξ\xiξ is revealed, and a wait-and-see (recourse) decision yyy is chosen afterwards, against the worst case of ξ\xiξ in an uncertainty set Ξ\XiΞ. When the recourse is binary — routing, scheduling, facility opening, emergency…

7 thms4 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization IV: On a Polish Space, the Maximum-Transport-Cost Worst-Case Loss Equals E[sup{f(x) : c(X̂, x) ≤ ρ}]Research Paper

In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P^\widehat{\mathbb P}P. For a Wasserstein distance of finite order ppp, the ball constrains an average transport cost. The case p=∞p=\inftyp=∞ is different. The ∞\infty∞-Wasserstein distance …

16 thms4 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

Residuals-based distributionally robust optimization with covariate information 1: Wasserstein ER-DRO with the Enlarged Radius (10) Certifies Its Out-of-Sample Cost with Probability 1−αResearch Paper

Many operational decisions are made after observing covariates that carry information about the uncertainty: a retailer sets inventory after seeing weather and calendar features that predict demand, a grid operator commits generation after seeing a load forecast. The decision problem is a conditional stochastic program: choose z∈Zz\in\mathcal Zz∈Z to minimize …

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information I: Worst-Case CVaR Is Exact for Individual Chance Constraints with Concave or Quadratic LossesResearch Paper

A chance constraint asks that an uncertain constraint hold with high probability: a decision is acceptable if the loss L(ξ~)L(\tilde\xi)L(ξ~​) it incurs is nonpositive with probability at least 1−ϵ1-\epsilon1−ϵ. Chance constraints appear in portfolio selection, power-system dispatch, inventory control and engineering design, wherever an occasional violation is tolerable but…

18 thms4 active usersReviewed
Optimization·Captain: mikedeng1

Optimality Conditions and Finite Convergence of Lasserre's Hierarchy I: Under Archimedeanness, the Classical Optimality Conditions at Every Global Minimizer Imply Finite ConvergenceResearch Paper

Polynomial optimization asks for the global minimum of a polynomial fff over a set K⊆RnK \subseteq \mathbb R^nK⊆Rn cut out by polynomial equations and inequalities. It contains nonconvex quadratic programming, max-cut, and many problems from control and engineering. Lasserre's hierarchy (Lasserre 2001) replaces this problem by a sequence of semidefinite programs…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationMachine Learning·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games I: If Every Player Runs Optimistic FTRL with Step Size 1/(2(n−1)), the Sum of All Players' Regrets Is at Most 2n(n−1)RResearch Paper

When the players of a game repeatedly adjust their strategies with no-regret learning algorithms, the empirical distribution of play converges to a coarse correlated equilibrium, and in smooth games the average social welfare approaches the price-of-anarchy guarantee of the game (Roughgarden 2009). For generic no-regret algorithms such as Hedge the…

9 thms4 active usersReviewed
Bandit AlgorithmsProbability·Captain: mikedeng1

A Primal-Dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint: The Primal-Dual Learning Algorithm Has Regret at Most C(log n)^(2+δ) n^(−1/2)Research Paper

A firm selling a fixed stock of a perishable product over a finite season must set prices without knowing how demand responds to them. Online retail and travel platforms often see a customer's segment before quoting a price, so they can price-discriminate across consumer types. Learning a separate demand curve for each type, however, seems to cost more…

21 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Intrinsic Robustness of the Price of Anarchy I: Every Coarse Correlated Equilibrium of a Smooth Game Has Expected Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper

The price of anarchy (POA) of a game measures how much selfish behaviour costs: it is the ratio between the largest cost of an equilibrium and the cost of an optimal outcome, for a nonnegative objective such as the sum of the players' costs. Since Koutsoupias and Papadimitriou (1999) and Roughgarden and Tardos (2002), POA bounds have been proved for…

12 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning IX: Cover's Universal Portfolio with Uniform or Dirichlet(1/2) Prior Has Logarithmic Regret Against Constantly Rebalanced PortfoliosTextbook

A portfolio manager chooses fractions of current wealth to place in several stocks before seeing that day’s market gains. The gains need not follow a statistical model: a sequence may be selected adversarially, with some stocks losing all value on a given day. A useful benchmark is the best constantly rebalanced portfolio, which holds the same fractions…

9 thms4 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: mikedeng1

Joint Assortment Optimization and Customization under a Mixture of Multinomial Logit Models 1: Augmented Greedy Earns a (1 − 1/e) Fraction of the Optimal Revenue from the Complete Customer TypesResearch Paper

Retailers that carry a limited range of products often know something about a customer before choosing which of those products to display. The customized assortment problem asks which products to carry when the displayed assortment may be tailored to the arriving customer's type. This separates the first-stage capacity decision from the later offer…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

Greed Works – Online Algorithms For Unrelated Machine Stochastic Scheduling 2: Greedy Assignment With Nominal Start Times Is (7.216 + 3.608Δ)h(Δ)-Competitive in the Online-Time ModelResearch Paper

Scheduling jobs on parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 2: Selling Two I.I.D. Goods Separately Guarantees at Least e/(e + 1) ≈ 73% of the Optimal RevenueResearch Paper

A seller with several goods can sell them one at a time or offer a mechanism that links allocation and payment across goods. Separate selling asks the seller to solve a one-good pricing problem for each item. A general mechanism can offer lotteries and menus whose outcomes depend on the buyer's whole valuation vector. The difference matters because the…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 5: Bundling Is Optimal for Two I.I.D. Goods Whose Density on [a, ∞) Satisfies x f′(x) + (3/2) f(x) ≤ 0Research Paper

A seller with several goods and a single buyer of unknown, additive valuation faces the multi-dimensional revenue maximization problem. For one good the answer is classical: by Myerson's theorem (Myerson 1981) a single posted price is optimal. For two or more goods no such simplification exists in general: optimal mechanisms may randomize, may offer menus…

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainProbability·Captain: mikedeng1

Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities 1: The Belief MDP Satisfies Assumption (W*) Under Total-Variation-Continuous ObservationsResearch Paper

A partially observable Markov decision process (POMDP) models a controller that cannot see the state of the system it steers, only noisy observations of it. Inventory control with unrecorded demand, machine maintenance with imperfect inspection, and target tracking from sensor readings all have this form. The standard way to solve a POMDP is to replace it…

16 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Regret in Online Combinatorial Optimization I: For Every Learning Rate the Exponentially Weighted Forecaster EXP2 Has Full-Information Regret at Least 0.01 d^{3/2}√n on Some Action SetResearch Paper

Online combinatorial optimization is a repeated game in which a learner selects, round after round, a structured object (a subset of fixed size, a path, a matching, a spanning tree) encoded as a 0/1 vector, and an adversary assigns a cost to every coordinate. It models routing, ranking, scheduling and many other sequential decision problems in operations…

7 thms4 active users
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization 1: Empirical Burg-Ball DRO Bounds Cover E[h(x;ξ)] with Probability Tending to 1 − αResearch Paper

Stochastic programs and chance-constrained models in operations research contain expectations of the form

14 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals I: Under Random Arrival Order, Nonadaptive Thresholds Earn a 1 − 1/e Fraction of E[max Xᵢ]Research Paper

In a prophet inequality, a gambler sees prizes one at a time and must decide when to stop, while a prophet knows every realization and takes the largest. A stopping guarantee compares the gambler’s expected prize with the prophet’s. The order of arrival changes the problem: here the prizes are independent but can have different distributions, and every…

12 thms4 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals II: For I.I.D. Variables, Adaptive Thresholds Achieve E[max Xᵢ] ≤ β*·E[X_t] with β* ≈ 1.341Research Paper

A prophet inequality compares a gambler who sees nonnegative random rewards X1,…,XnX_1,\ldots,X_nX1​,…,Xn​ one at a time, and must accept or reject each on arrival, with a prophet who knows all values in advance and simply takes max⁡iXi\max_i X_imaxi​Xi​. For independent and identically distributed (i.i.d.) rewards the question is the best constant β\betaβ such that some online rule always…

17 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness III: With Additive Valuations, Donating the Pool to an Unenvied Agent Yields a 4/7-Groupwise-Maximin-Share AllocationResearch Paper

When indivisible goods are shared among people, comparing each person's bundle with another person's bundle is only one way to judge fairness. A second test asks whether a group could repartition the goods it collectively received so that one of its members would reliably obtain more. Groupwise maximin share (GMMS) makes this test for every subgroup. It…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness I: Under Monotone Valuations an EFX Allocation Exists Whose Unenvied Pool Has Fewer Goods Than There Are Unenvied AgentsResearch Paper

Allocating indivisible goods fairly is difficult because a single good can change how an agent compares two bundles. Exact envy-freeness can be impossible (one good, two agents), so the field works with relaxations. Envy-freeness up to any good (EFX) requires each agent to prefer her own bundle to every other agent's bundle after any one good of that other…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

A game-theoretic approach to computation offloading in mobile cloud computing II: The VI Map of the Offloading GNEP Is Monotone When the Cloudlet Is Not OverloadedResearch Paper

Mobile devices run applications whose computational demand often exceeds what a battery-powered processor can serve with acceptable delay. Computation offloading sends part of the work elsewhere: to a cloudlet, a small cluster of servers one wireless hop away, or to a distant cloud reached through the wide-area network. When many users share one cloudlet,…

10 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 3: ARC(S) Reaches −λ_min(QᵀBQ) ≤ ε in O(ε^(−3)) IterationsResearch Paper

Unconstrained minimization of a smooth nonconvex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R is the core subproblem of most nonlinear optimization software. Methods that only drive the gradient to zero may stall at saddle points, so a second-order guarantee (approximately nonnegative curvature) is the natural target for nonconvex problems. Worst-case evaluation…

15 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 2: ARC(S) Reaches ‖g‖ ≤ ε in O(ε^(−3/2)) IterationsResearch Paper

Second-order methods for smooth nonconvex minimization are used in practice because they converge in far fewer iterations than gradient descent, yet for a long time their worst-case guarantee from an arbitrary starting point was no better than that of steepest descent. Nesterov and Polyak (Math. Program. 108, 2006) showed that adding a cubic term to…

13 thms4 active usersReviewed
PreviousPage 22 of 145Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me