Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

A coordinated effort to formalize the mathematics of operations research in Lean 4.

Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.

3528 completed missions

Missions

1976–2000 of 3528
Open1284Completed3528All4812
🏆Completed
CombinatoricsComplexity TheoryDiscrete Geometry+2·Captain: mikedeng1

Exponential Lower Bounds for Polytopes in Combinatorial Optimization: The TSP Polytope Has Extension Complexity 2^Ω(√n)Research Paper

Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…

21 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in O(n log n) or O(n) Time: Minimal Optimal Predecessor Lists Are Characterized by Strictly Increasing BreakpointsResearch Paper

The dynamic lot size model asks when, and how much, to order of a single item over a planning horizon of nnn periods with known, time-varying demands, setup costs, unit order costs and holding costs. It is the textbook model of production planning and the building block of material requirements planning, multi-item scheduling and many decomposition schemes…

16 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems: Algorithm OPT Returns an Optimal Reorder Point and Order QuantityResearch Paper

(r, Q) policies are the standard replenishment rule for a single item under continuous review: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder point rrr, an order of size QQQ is placed. They are known to be optimal in the classical models with Poisson or compound renewal demand, constant or exogenous lead…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 3: Order-Oblivious Posted Prices 2-Approximate the Optimal Revenue under a Uniform Matroid ConstraintResearch Paper

Myerson's optimal auction (Myerson 1981) maximizes a seller's expected revenue when buyers have independent private values, but it is a sealed-bid mechanism: every buyer reports a value, and the allocation and payments are computed from all reports at once. Real sellers more often post prices: buyers arrive, each sees a take-it-or-leave-it price, and buys…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VIII: A Vertex Schedule Maximizes the Net Present Value iff Its Spanning-Tree Subprojects Have the Right SignsTextbook

Long-running projects such as construction, plant engineering or software development involve payments to and from the contractor at many points in time: disbursements when activities are carried out, progress payments when milestones are reached. When the planning horizon is long, money received later is worth less, and the natural financial objective is…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

One-Machine Sequencing to Minimize Certain Functions of Job Tardiness I: SPT Order Minimizes Total Tardiness When Each Due Date Plus Processing Time Is at Most the Next SPT Completion TimeResearch Paper

A shop that promises delivery dates is judged by how late its orders are, not by how early. For a single machine processing nnn jobs that are all available at time 000, the total tardiness of a processing order,

8 thms3 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization·Captain: mikedeng1

On the Variational Principle II: Under Linearly Independent Active Constraint Gradients, a Bounded-Below Problem Has ε²-Optimal Feasible Points Satisfying the Lagrange Multiplier Rule up to εResearch Paper

The classical Lagrange multiplier rule and its inequality-constrained form, the Karush–Kuhn–Tucker (KKT) conditions, are necessary conditions satisfied at a minimizer of a constrained problem. In finite dimensions, a continuous function bounded below on a closed bounded feasible set attains its minimum, so the rule describes an actual point. In an…

7 thms3 active usersReviewed
🏆Completed
AnalysisCalculus of VariationsFunctional Analysis+1·Captain: mikedeng1

On the Variational Principle I: Near Every ε-Minimizer of a Lower Semicontinuous Function Bounded Below on a Complete Metric Space Lies a Strict Minimizer of F + (ε/λ)d(v, ·)Research Paper

A function that is bounded below need not attain its infimum: exe^xex on R\mathbb{R}R has infimum 000 and no minimizer. The classical "variational principle" says that at a minimizer uˉ\bar uuˉ of a differentiable functional, F′(uˉ)=0F'(\bar u)=0F′(uˉ)=0. Without compactness there may be no minimizer, and the principle has nothing to say. In 1974 Ivar Ekeland showed that a weaker…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Dimensioning Large Call Centers I: The Rationalized Staffing Function Is Asymptotically OptimalResearch Paper

A call center with NNN agents facing Poisson arrivals at rate λ\lambdaλ and exponential service at rate μ\muμ is the M/M/N (Erlang-C) queue. Choosing NNN trades the cost of agents against the cost of customers waiting, and in practice it is done with the square-root safety-staffing rule N≈R+yRN \approx R + y\sqrt RN≈R+yR​, where R=λ/μR = \lambda/\muR=λ/μ is the offered load. Borst,…

22 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory IX: Kingman's Upper Bound on the G/G/1 Queue WaitTextbook

The single-server queue with general independent interarrival and service times, the G/G/1 queue, is the basic model of a congested resource: a machine, a link, a checkout. For Markovian arrivals or services the mean wait has a closed form (the Pollaczek–Khintchine formula for M/G/1, the geometric law for G/M/1). For general distributions it has none, and…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Multicut Algorithm for Two-Stage Stochastic Linear Programs 2: Multicut for Simple Recourse Stops Within J·m2 + 1 IterationsResearch Paper

Two-stage stochastic linear programs model decisions taken before uncertainty is resolved (first stage) and corrected afterwards at a cost (second stage, the recourse). The standard solution method for problems with finitely many scenarios is the L-shaped method of Van Slyke and Wets (1969), an outer linearization in the style of Benders decomposition: a…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games IV: For Symmetric Games the Maximum Social Cost Price of Anarchy Is at Most 5/2Research Paper

The price of anarchy measures how much a system of selfish agents loses compared with a centrally optimized one: it is the worst ratio, over all Nash equilibria, between the social cost of the equilibrium and the optimal social cost. Koutsoupias and Papadimitriou introduced it in 1999 (Worst-case equilibria, STACS 1999), and bounding it for routing and…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games I: The Pure Price of Anarchy of the Average Social Cost Is 5/2Research Paper

When many independent users share a resource whose cost grows with use (links of a network, servers, machines), each user chooses for itself, and the outcome is a Nash equilibrium rather than a socially optimal allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures the cost of this decentralisation: the worst…

7 thms3 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningProbability+1·Captain: mikedeng1

The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 1: ℓ2 Error Bound for Sparse Parameters under the Uniform Uncertainty PrincipleResearch Paper

In many statistical applications the number of unknown parameters ppp is far larger than the number of observations nnn: gene-expression studies with tens of samples and thousands of genes, imaging problems with fewer measurements than pixels, and nonparametric curve estimation from finitely many noisy samples. Least squares is useless in this regime, since the…

9 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainOptimization+1·Captain: mikedeng1

Reinforcement Learning: An Introduction XII: The Policy Gradient TheoremTextbook

Policy gradient methods learn a parameterized policy π(a∣s,θ)\pi(a \mid s, \theta)π(a∣s,θ) directly, by stochastic gradient ascent on a scalar performance measure J(θ)J(\theta)J(θ), instead of deriving the policy from learned action values. They are how reinforcement learning handles continuous action spaces, stochastic optimal policies and prior knowledge built into the policy's…

14 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Multicut Algorithm for Two-Stage Stochastic Linear Programs 1: Worst-Case Bound on Multicut Major IterationsResearch Paper

Two-stage stochastic linear programs with recourse are a standard model for planning under uncertainty: a first-stage decision xxx is taken before a random outcome ξ\xiξ is observed, and a second-stage (recourse) decision yyy corrects for it afterwards at a cost. When ξ\xiξ has finitely many realizations, the problem is a large but structured linear program, and…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 4: Restarting a Bounded-Cost Algorithm Is (1+ε)α-Competitive in Games of Finite DiameterResearch Paper

Competitive analysis compares an online algorithm, which must answer each request before seeing the next, with the optimal off-line solution of the same request sequence. Ben-David, Borodin, Karp, Tardos and Wigderson (Algorithmica 11, 1994) set up a general framework, request-answer games, in which paging, the KKK-server problem and metrical task systems are…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 3: An Augmented Potential Function Yields an Explicit Deterministic α∘β-Competitive AlgorithmResearch Paper

Competitive analysis measures an online algorithm, which must answer each request before seeing the next, against the best off-line answer to the whole request sequence. Randomized online algorithms are often much better than deterministic ones against an oblivious adversary, who fixes the requests in advance; the paging problem is the standard example.…

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchStochastic Systems·Captain: mikedeng1

Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance II: An O(n²) Extended Formulation of the Multiclass M/M/1 Performance PolymatroidResearch Paper

A single server shared by several classes of customers is the basic model of scheduling under uncertainty: jobs of different types arrive at random, need random amounts of work, and a scheduler decides at every moment which type to serve. A classical way to optimize such a system, the achievable region approach, describes the set of all performance vectors…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 3: Fractional Double Greedy on the Multilinear Extension Achieves 1/2 of the OptimumResearch Paper

Unconstrained submodular maximization (USM) asks for a subset SSS of a finite ground set N\mathcal NN maximizing a nonnegative submodular function fff. It contains Max-Cut, Max-DiCut and maximum facility location as special cases, and it is the basic subproblem of many constrained submodular maximization algorithms. Because fff is given only through a value oracle,…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 1: α-Competitiveness Against Adaptive On-Line and β Against Oblivious Adversaries Give a Deterministic α∘β-Competitive AlgorithmResearch Paper

An online algorithm must answer each request before it sees the next one. Its performance is compared with an optimum that may choose all its answers after seeing the complete request string. Randomization can improve an online algorithm's guarantee when the request string is fixed in advance. The comparison changes when an adversary chooses later requests…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 2: The Bound α∘β Against Adaptive Off-Line Adversaries Is TightResearch Paper

An on-line algorithm must answer each request as it arrives, without knowing the requests to come; paging, caching, the kkk-server problem and metrical task systems are standard examples. Its quality is measured by competitive analysis: its cost is compared with the cost of an optimal off-line solution that knows the whole request sequence. For randomized…

9 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Gradient Convergence in Gradient Methods with Errors II: With Zero-Mean Stochastic Errors, Almost Surely Either f(x_t) → −∞ or f(x_t) Converges and ∇f(x_t) → 0Research Paper

Stochastic gradient methods minimize a function fff when only noisy estimates of its gradient are available: each step moves along a descent direction corrupted by random noise. They are the standard training algorithm for neural networks and the basic tool of stochastic approximation, and the question every user faces is what can be guaranteed when fff is nonco…

4 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction VII: The Error Reduction Property of n-step ReturnsTextbook

Temporal-difference (TD) learning estimates the value of a policy by moving a current estimate toward a target built from observed rewards and from the estimate itself. Chapter 7 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) interpolates between the two extreme targets of the preceding chapters: the one-step TD…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningMechanism Design·Captain: mikedeng1

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 2: Neutral Affine Maximizers Have Pseudo-Dimension at Least ⌊n/2⌋Research Paper

In data-driven algorithm design, an algorithm or mechanism comes with a vector of tunable parameters ρ\rhoρ, and the parameters are chosen by optimizing average performance over sample instances drawn from an unknown distribution. How many samples suffice for the empirical optimum to be near-optimal in expectation is governed by the pseudo-dimension of the…

6 thms3 active usersReviewed
PreviousPage 80 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36595448
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82897261

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