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.

4812 missions

Missions

2126–2150 of 4812
Open1268Completed3544All4812
🏆Completed
Functional AnalysisProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces IX: Suprema of Linear Forms in Bounded Independent Variables — P(|Z − M| ≥ u) ≤ 4 exp(−u²/(4σ²))Textbook

A family of linear forms turns independent observations into a single random maximum. Examples include the largest value of a collection of statistical scores and the norm of a random vector sum, which can itself be expressed through the continuous dual of a normed space. A bound for each form separately does not automatically control the supremum over an…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Primal-dual subgradient methods for convex problems 1: Dual Averaging Keeps the Gap Below β_{k+1}D + (1/2σ)Σλᵢ²‖gᵢ‖²_*/βᵢ and Its Iterates BoundedResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth convex function when only a black-box oracle returning one subgradient per query is available. In the classical method the new subgradient enters the iterate with a weight that decreases over time, so information collected late is counted less than information collected early, and the method…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces VIII: The Longest Increasing Subsequence — Gaussian Concentration of L_N around Its Median MTextbook

Pick NNN independent points X1,…,XNX_1, \dots, X_NX1​,…,XN​ uniformly in [0,1][0,1][0,1] and let LNL_NLN​ be the length of the longest increasing subsequence. Because the points are almost surely distinct, LNL_NLN​ has the law of the longest increasing subsequence of a uniform random permutation of {1,…,N}\{1, \dots, N\}{1,…,N}. This is Ulam's problem, one of the most studied random combinatorial quantities.…

8 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 2: The Adaptive-Step Algorithm in N∞(β) or N∞⁻(β) with γ ≤ 2(1 − β) Attains Precision t in O(nt) IterationsResearch Paper

Primal-dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal-dual pairs whose complementarity products xjsjx_js_jxj​sj​ are all equal. Every such method confines its iterates to a neighbourhood of that path, and the neighbourhood governs both the theory and the practice. The first primal-dual…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces II: The Two-Point Space — an N-Free Exponential Bound for the One-Sided Hamming Distance under a Second MeasureTextbook

The concentration of measure phenomenon says that in a product probability space a set of probability not too small is "large" in the sense that most points lie within a small distance of it. M. Talagrand's 1995 memoir Concentration of measure and isoperimetric inequalities in product spaces develops this phenomenon through exponential moment bounds for…

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

Regenerative Stochastic Processes 4: Cumulative Processes on the Same Regeneration Points Are Jointly Asymptotically NormalResearch Paper

Many quantities in queueing, inventory and reliability models are additive functionals of a regenerative process: the total work processed by a server up to time ttt, the cost accumulated by an inventory policy, the time a machine spends broken. Each such quantity grows by independent, identically distributed amounts over the cycles between successive…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisNumerical Analysis+2·Captain: mikedeng1

Régularisation d'inéquations variationnelles par approximations successives II: The Proximal Regularization of a Convex Minimization Problem Is a Minimizing SequenceResearch Paper

The proximal point algorithm replaces a hard optimization or equilibrium problem by a sequence of better-conditioned ones: from the current point xnx^nxn it solves the original problem with a quadratic penalty ∥x−xn∥2\|x-x^n\|^2∥x−xn∥2 added, and takes the solution as xn+1x^{n+1}xn+1. The method is a building block of modern convex optimization. Augmented Lagrangian methods,…

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

A 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales: The Dual-Balancing Policy Costs at Most Twice Any Nonanticipatory Policy under Independent DemandsResearch Paper

Inventory systems in which unmet demand is lost, not backlogged, are the norm in retail: a customer who finds an empty shelf buys elsewhere. With a positive lead time LLL between ordering and delivery, the optimal policy for such a system depends on the entire pipeline of outstanding orders, so dynamic programming is intractable beyond small LLL. Optimal…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization: The Matrix Shrinkage Fixed Point Iteration Converges to an Optimal Solution of the Nuclear Norm Regularized ProblemResearch Paper

Many estimation problems ask for a matrix of low rank that is consistent with a small number of linear measurements: completing a partially observed ratings matrix, identifying a low-order linear system, or embedding points from a few pairwise distances. Rank minimization under linear constraints is NP-hard, and the standard convex surrogate replaces the…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Stochastic Convex Programming: Basic Duality 2: With a Bounded Second-Stage Set the Intrinsic First-Stage Problem Coincides with the One Induced by P and Recourse Is AttainedResearch Paper

Two-stage stochastic programming with recourse models a decision taken in two steps: a first-stage decision x1x_1x1​ is fixed before a random outcome sss is observed, and a recourse decision x2(s)x_2(s)x2​(s) is taken afterwards, once sss is known. The model goes back to Dantzig (1955) and Beale (1955) and is the basic template of stochastic optimization in operations…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Quality Control under Markovian Deterioration 3: Sufficient Conditions for a Three-Region Optimal Policy and for an Optimal Policy That Never InspectsResearch Paper

Inspection and revision cost money, but continued production can allow a deteriorating process to remain in a costly state. A controller therefore needs a rule that converts incomplete information about the process into an action. Ross's two-state model makes that decision precise: the process can be good or bad, the bad state persists until revision, and…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Quality Control under Markovian Deterioration 2: Never Inspecting or Revising Is Optimal Exactly When R ≥ C/(1 − β(1 − π))Research Paper

A production process can deteriorate without an operator seeing its current condition. Producing a unit, inspecting the process, and revising the process have different immediate costs and different effects on what can be known or controlled next period. The operator therefore needs a rule based on a belief about deterioration, rather than on the hidden…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 2: Enumerating Long Assignments and Rounding the LP Gives a (1 + ε)-Approximation for MakespanResearch Paper

Scheduling independent jobs on unrelated parallel machines to minimize the makespan is one of the basic NP-hard problems of scheduling theory: each job has its own processing time on each machine, with no relation between machines, and the goal is to finish all jobs as early as possible. When the number of machines is part of the input, Lenstra, Shmoys and…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory+1·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 4: The m-Cube Has Isometric Dimension mResearch Paper

A finite graph has distances defined by the lengths of its shortest paths. Representing those distances inside a normed vector space lets geometric language describe a combinatorial object, but the number of coordinates required can depend sharply on the graph. The isometric dimension asks for the smallest dimension of any real normed space that preserves…

11 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Strongly Regular Generalized Equations IV: Strong Second-Order Sufficiency and Linearly Independent Binding Gradients Make the KKT Generalized Equation Strongly RegularResearch Paper

A nonlinear program is rarely solved once. Its data are estimated, rounded, or varied on purpose in a parametric study, and an algorithm such as sequential quadratic programming replaces it at every iteration by a nearby linearised problem. Both uses need the same fact: near a solution, the Karush–Kuhn–Tucker (KKT) system should have exactly one solution…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

The Four-Colour Theorem: Birkhoff's Lemma (6.4) — Every Non-Empty Consistent Set of Edge-Colourings of a Ring of Length 5 Meeting ℰ Includes One of 𝒞ᵢ, 𝒟ᵢ, ℰResearch Paper

The Four-Colour Theorem was proved by Appel and Haken (1976–77) and re-proved by Robertson, Sanders, Seymour and Thomas (RSST, 1997) with a simpler, fully computer-checkable argument. Both proofs rest on reducibility: a configuration is reducible when every 4-colouring of the ring around it can be modified, by Kempe-chain recolouring, into one that extends…

6 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations II: A Semismooth, Strongly BD-Regular Zero That Is a Limit Point of the Damped Newton Method Attracts It with Unit StepsResearch Paper

Many problems of optimization and equilibrium reduce to a system of nonsmooth equations F(x)=0F(x)=0F(x)=0 with F:Rn→RnF:\mathbb R^n\to\mathbb R^nF:Rn→Rn locally Lipschitz but not differentiable: nonlinear complementarity problems written as min⁡{h(x),f(x)}=0\min\{h(x),f(x)\}=0min{h(x),f(x)}=0, variational inequalities through the normal map, and Karush–Kuhn–Tucker systems of constrained programs. Newton's method…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations I: At a Semismooth, Strongly BD-Regular Zero the ∂_B Newton Method Converges Superlinearly and ‖F‖ Decreases SuperlinearlyResearch Paper

Many problems of operations research reduce to a system of nonsmooth equations F(x)=0F(x)=0F(x)=0 with F:Rn→RnF:\mathbb R^n\to\mathbb R^nF:Rn→Rn locally Lipschitz but not differentiable: the nonlinear complementarity problem h(x)≥0h(x)\ge 0h(x)≥0, f(x)≥0f(x)\ge0f(x)≥0, h(x)Tf(x)=0h(x)^Tf(x)=0h(x)Tf(x)=0 becomes F(x)=min⁡{h(x),f(x)}=0F(x)=\min\{h(x),f(x)\}=0F(x)=min{h(x),f(x)}=0 componentwise, and variational inequalities, KKT systems and max-type equations admit similar…

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

Job Matching, Coalition Formation, and Gross Substitutes 3: A Coalition Technology Satisfying Gross Substitutes for m + 1 Identical Firms Has a Strict Core AllocationResearch Paper

Workers can form groups and produce an output that they divide through salaries. A group may object to a proposed allocation when it can pay all of its members at least as much and one member more. The central question is whether any allocation survives every such objection. Kelso and Crawford's 1982 paper gives a sufficient condition based on how an…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 4: Without Ties the Salary-Adjustment Process Reaches the Firm-Optimal Discrete Strict Core AllocationResearch Paper

Labor markets match heterogeneous workers to heterogeneous firms, and the terms of each match — the salary — are negotiated. Kelso and Crawford (Econometrica 50 (1982)) studied such a market in which a firm may hire many workers, its output depends on the whole set it hires, and salaries are set worker by worker. Their model contains the marriage problem of…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 3: Shifting and Scaling the Processing Times Changes Neither the Optimal Sequence nor the Branch-and-Bound PathResearch Paper

Branch and bound was introduced for integer programming by Land and Doig (1960) and for the travelling salesman problem by Little, Murty, Sweeney and Karel (1963). Ignall and Schrage (1965) were among the first to apply it to machine scheduling. They give lower bounds for two permutation flow-shop problems: the makespan on three machines, and the mean…

15 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 2: Under Gross Substitutes Every Job-Matching Market with Continuous Salaries Has a Strict Core AllocationResearch Paper

Labour markets match workers to firms that hire teams: a firm's output depends on the whole set of workers it employs, while each worker holds one job. A salary agreement is stable when no firm and group of workers can renegotiate among themselves to the benefit of all of them. Shapley and Shubik (1971) showed that such stable outcomes exist when each firm…

6 thms3 active usersReviewed
🏆Completed
Control TheoryDynamical SystemsOperations Research·Captain: mikedeng1

Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 2: Stable and Unstable Modes Coexist Under Clearing on a Two-Part-Type SystemResearch Paper

Flexible manufacturing systems are often scheduled by simple distributed rules: each machine looks only at its own buffers and decides, in real time, which part type to work on next. Switching from one part type to another costs a set-up time during which the machine produces nothing, so a natural rule is to work on a buffer until it is empty and only then…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem 2: For g = 0 ≤ f, the Tour ψ′ Minimizes the Largest Changeover CostResearch Paper

A machine whose condition is described by one real number — the temperature of a furnace, the setting of a cutting knife — must process NNN jobs in some order. Job iii must be started in state AiA_iAi​ and leaves the machine in state BiB_iBi​; moving the state between jobs costs money. Ordering the jobs so that the machine returns to its starting job after the last one…

9 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Contact Interactions on a Lattice II: If λₖ/μ < k/(2d − 1), the Expected Size of a Contact Process Is Integrable in TimeResearch Paper

The contact process is the basic model of an infection spreading on a graph: infected sites recover at a constant rate, and healthy sites are infected at a rate that depends on how many of their neighbours are infected. T. E. Harris introduced it in Contact Interactions on a Lattice (Ann. Probab. 2, 1974, doi:10.1214/aop/1176996493), and it became one of…

13 thms3 active usersReviewed
PreviousPage 86 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5206499
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36595448
5NINickrobbins953288156
6VEvebis25800
7FIfizzyinc321715
8SHshivm17500
9SCShuze Chen9455324
10KMkmehltretter82933261

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