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 OptimizationOptimizationProbability·Captain: mikedeng1

Introduction to the Scenario Approach II: Violation Guarantees after Discarding k ConstraintsTextbook

Decisions under uncertainty are often required to satisfy a constraint θ∈Θδ\theta \in \Theta_\deltaθ∈Θδ​ that depends on a random parameter δ\deltaδ, and requiring it for every possible δ\deltaδ is usually too conservative or infeasible. The scenario approach replaces the unknown distribution of δ\deltaδ by NNN independent samples (scenarios) and enforces only the sampled…

13 thms2 active usersReviewed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Introduction to the Scenario Approach IV: The FAST Algorithm Keeps the Beta Bound and Adds a Factor (1−ε)^{N₂}Textbook

The scenario approach turns an optimization problem under uncertainty into a finite, data-driven program: sample NNN instances of the uncertain parameter, optimize against all of them, and certify how often the resulting design fails on a new instance. Its main guarantee (Theorem 3.7 of Campi and Garatti's Introduction to the Scenario Approach) bounds the…

6 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Adaptive Data-Driven Inventory Control with Censored Demand Based on Kaplan-Meier Estimator: Almost-Sure Convergence of KM-Myopic Orders to the Newsvendor Optimal SetResearch Paper

A retailer who restocks a perishable product every period faces the newsvendor problem: order too much and each leftover unit costs h>0h>0h>0, order too little and each unmet unit of demand costs b>0b>0b>0. If the demand distribution were known, the optimal order would be a quantile of it. In practice the distribution is unknown and has to be learned from sales data,…

11 thms2 active usersReviewed
Algorithmic Game TheoryDynamic Programming·Captain: mikedeng1

Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor: Explicit Iteration Bound for Strategy IterationResearch Paper

Two-player turn-based stochastic games (2TBSGs) model a zero-sum contest on a finite graph with random transitions: in each state one player chooses an action, pays its cost, and a lottery chooses the next state. The minimizer and the maximizer both evaluate the total discounted cost. The model contains Markov decision processes (one player), simple…

24 thms2 active usersReviewed
AnalysisProbabilityStochastic Systems·Captain: mikedeng1

Elements of Queueing Theory Ib: Ergodicity and Stochastic IntensityTextbook

Chapter 1 of Baccelli and Brémaud's Elements of Queueing Theory has two halves. The first builds Palm calculus from the Matthes definition of P⁰_N and reaches the Swiss army formula. This mission is the second: §§1.6, 1.8 and 1.9, which supply the two things the rest of the book runs on.

13 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Strategyproof Approximation of the Minimax on Networks 2: No Strategyproof Randomized Mechanism Beats 2 - o(1) on TreesResearch Paper

A public facility (a fire station, a hospital, a server) is to be placed on a road network, and the people it serves report their own locations. When the planner wants to minimise the distance to the farthest user (the minimax or egalitarian objective, in the sense of Rawls), each user has an incentive to misreport so as to pull the facility towards…

9 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Strategyproof Approximation of the Minimax on Networks 1: A Strategyproof 3/2-Approximation Mechanism on the CircleResearch Paper

A facility — a fire station, a server, a meeting point — must be placed on a network, and every user of the network reports where they are. When the planner cares about the worst-off user, the objective is the minimax: minimize the largest distance from the facility to a user. The reports are private information, so a user may misreport a location to pull…

13 thms2 active usersReviewed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Introduction to the Scenario Approach III: The Risks of the Empirical Costs Follow an Ordered Dirichlet DistributionTextbook

A scenario program replaces an uncertain optimization problem by its worst case over finitely many sampled instances. In its simplest form it reads

10 thms2 active usersReviewed
Optimization·Captain: mikedeng1

Global Convergence of Splitting Methods for Nonconvex Composite Optimization III: For Semi-Algebraic Problems the ADMM Sequence Converges and Has Finite LengthResearch Paper

The alternating direction method of multipliers (ADMM) is a standard method for problems of the form min⁡xh(x)+P(Mx)\min_x h(x)+P(\mathcal Mx)minx​h(x)+P(Mx), in which a smooth loss hhh is composed with a structured, possibly nonsmooth regularizer PPP through a linear map M\mathcal MM. Its convergence theory was developed for convex problems, yet it is routinely run on nonconvex ones: sparse…

17 thms2 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: mikedeng1

Value of Information in Bayesian Routing Games II: Equilibrium Adoption Rates of Information Systems Are the Minimizers of the Equilibrium PotentialResearch Paper

Traffic information systems (TIS) such as navigation apps send drivers private, noisy signals about the state of the road network: incidents, weather, closures. When several such systems coexist, their subscribers act on different information, and the congestion each population experiences depends on how all of them route. A question then arises for…

10 thms2 active usersReviewed
CombinatoricsLinear OptimizationOptimization·Captain: mikedeng1

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem I: ALGORITHM 1, Linear Grouping with LP Rounding, Is an Asymptotic Approximation SchemeResearch Paper

One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in (0,1)(0,1)(0,1). It is the model behind cutting stock (cutting rolls of paper or steel to ordered widths), memory and file allocation, and batch scheduling on identical machines, and it is NP-hard. Its algorithmic study is therefore about approximation:…

16 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Diffusion approximations for open queueing networks with service interruptions 2: jump-diffusion heavy-traffic limit for long up and down timesResearch Paper

Servers in manufacturing lines, communication links and service systems break down, are taken offline for maintenance, or go on vacation. When the interruptions are rare but long, they dominate congestion. A single down period can build a backlog that takes a long time to clear, and in a network that backlog propagates downstream. Standard heavy-traffic…

10 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks IV: Fluid Equations for Non-Idling, Priority and FCFS ControlTextbook

Mission III's Theorem 6.2 — "fluid limit stability implies SPN stability" — converts a probabilistic stability question into a real-analysis question, but it only supplies the generic fluid equations (6.1)-(6.6), which hold under any control policy and therefore say nothing policy-specific: (6.1)-(6.6) alone never force a fluid path to reach zero. To…

9 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Graph Minors. V. Excluding a Planar Graph: Bounded Tree-Width without a Planar MinorResearch Paper

Tree-width measures how closely a graph resembles a tree. Graphs of bounded tree-width admit dynamic-programming algorithms for problems that are NP-hard in general (colouring, Hamiltonicity, and every property expressible in monadic second-order logic, by Courcelle's theorem), which is why the parameter is central to parameterized complexity and to…

29 thms2 active usersReviewed
CombinatoricsGraph TheoryOptimization+1·Captain: mikedeng1

Linear-Time Approximation for Maximum Weight Matching: The Approximation Guarantee of the Scaling AlgorithmResearch Paper

The maximum weight matching (MWM) problem asks, for a graph with edge weights, for a set of vertex-disjoint edges of largest total weight. It is a central problem of combinatorial optimization, with applications to transportation, assignment and scheduling, and as a subroutine for shortest paths, planar max cut, Chinese postman tours and metric TSP.…

12 thms2 active usersReviewed
Functional AnalysisProbability·Captain: mikedeng1

Conditional and Dynamic Convex Risk Measures I: Robust Representation of Conditional Convex Risk MeasuresResearch Paper

A convex risk measure assigns to a bounded financial position XXX (a random net payoff) a number ρ(X)\rho(X)ρ(X), interpreted as the capital that must be added to XXX to make it acceptable. The axiomatic theory began with coherent risk measures (Artzner, Delbaen, Eber and Heath, 1999) and was extended to convex ones by Föllmer and Schied (2002) and Frittelli and…

14 thms2 active usersReviewed
Control TheoryOptimization·Captain: mikedeng1

Optimizing Static Linear Feedback: Gradient Method II: The Gradient Flow Stays in the Sublevel Set and Converges Exponentially under State FeedbackResearch Paper

The linear-quadratic regulator (LQR) is the basic problem of optimal control: steer a linear system x˙=Ax+Bu\dot x = Ax + Bux˙=Ax+Bu so as to minimize an integrated quadratic cost of state and input. When the full state is measured, the optimal law is a static linear feedback u=−Kxu = -Kxu=−Kx obtained from an algebraic Riccati equation. When only an output y=Cxy = Cxy=Cx is measured, the…

13 thms2 active usersReviewed
CombinatoricsGraph TheoryOptimization·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity III: The Two-Machine Algorithm for Q2 with One Resource and Unit-Time Jobs Is OptimalResearch Paper

Many production and computing systems run jobs on parallel machines that also draw on a shared, limited resource: tools, workers, memory, power. Adding such a resource to a scheduling problem can change its complexity entirely. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the three-field classification α∣β∣γ\alpha\mid\beta\mid\gammaα∣β∣γ of Graham, Lawler,…

10 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Exit Problems for Spectrally Negative Lévy Processes and Applications to (Canadized) Russian Options I: Joint Laplace Transform of the Exit Time and Exit Position of the Reflected ProcessResearch Paper

A spectrally negative Lévy process is a process with stationary independent increments whose jumps are all downward: Brownian motion with drift plus a compound Poisson or infinite-activity stream of negative jumps. It is the standard model for a risk reserve that earns premiums continuously and pays claims in lumps, for a storage level or a queue workload…

16 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Subjectivity and Correlation in Randomized Strategies II: Subjective Events Let Both Zero-Sum Players Beat the ValueResearch Paper

In a two-person zero-sum game with objective randomization, whatever one player gains the other loses: the value vvv of the game is the most player 1 can guarantee and the least player 2 can hold him to, and no arrangement between the players can give player 1 more than vvv and player 2 more than −v-v−v at the same time. Aumann's 1974 paper (doi:10.1016/0304-4068(74…

9 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Online Decision Making with High-Dimensional Covariates: Regret Bound of the LASSO BanditResearch Paper

Many sequential decisions are personalised: a physician chooses a drug dose for each arriving patient, a platform chooses which offer to show each arriving user. Each decision is made after observing a vector of covariates describing the individual, and its outcome is observed only for the option chosen. This is the contextual (covariate) bandit problem,…

9 thms2 active usersReviewed
Algorithmic Game TheoryLinear Optimization·Captain: mikedeng1

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities I: Fisher Markets with an Equilibrium Have Rational Equilibrium Prices of Polynomial Bit SizeResearch Paper

A Fisher market is the simplest model of a market in which prices are set by supply and demand: buyers bring money, sellers bring goods, and a price vector is an equilibrium when every buyer, spending her money optimally at those prices, leaves every good exactly sold out. Computing equilibria is one of the central questions of algorithmic game theory,…

8 thms2 active usersReviewed
OptimizationProbabilityStatistics+1·Captain: mikedeng1

Acceleration of Stochastic Approximation by Averaging: Almost-Sure Convergence and Asymptotic Normality of the Averaged IterateResearch Paper

Stochastic approximation finds a root x∗x^*x∗ of an unknown map R:RN→RNR:\mathbb R^N\to\mathbb R^NR:RN→RN from noisy evaluations yt=R(xt−1)+ξty_t=R(x_{t-1})+\xi_tyt​=R(xt−1​)+ξt​, by the Robbins–Monro recursion xt=xt−1−γtytx_t=x_{t-1}-\gamma_ty_txt​=xt−1​−γt​yt​. It underlies stochastic gradient descent, recursive estimation in statistics, adaptive control and simulation-based optimization. The classical theory (Sacks 1958) shows…

10 thms2 active usersReviewed
Dynamic ProgrammingProbabilityStochastic Systems·Captain: mikedeng1

On the optimality equation for average cost Markov decision processes and its validity for inventory control: The Average-Cost Optimality Equation for Setup-Cost Inventory ControlResearch Paper

Average-cost criteria are standard in inventory, queueing and maintenance models that run indefinitely. For a Markov decision process (MDP), the central object is the average-cost optimality equation (ACOE). It couples a constant www (the optimal long-run cost per period) with a relative value function u~\tilde uu~. A stationary policy that attains the minimum in…

12 thms2 active usersReviewed
CombinatoricsDiscrete GeometryLinear Optimization·Captain: mikedeng1

On Sub-determinants and the Diameter of Polyhedra: A Polynomial Diameter Bound in the Largest SubdeterminantResearch Paper

The combinatorial diameter of a polyhedron is the largest distance, in its vertex-edge graph, between two vertices. It is a lower bound on the number of pivots any edge-following method such as the simplex method needs in the worst case, which is why the polynomial Hirsch conjecture — the diameter of P={x∈Rn:Ax≤b}P = \{x \in \mathbb{R}^n : Ax \le b\}P={x∈Rn:Ax≤b} is bounded by a…

11 thms2 active usersReviewed
PreviousPage 33 of 39Next

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