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

2251–2275 of 4812
Open1250Completed3562All4812
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Subadditive Ergodic Theory 6: The Ulam–Hammersley Constant of the Longest Increasing Subsequence Satisfies (8/π)^{1/2} ≤ c ≤ δ^{1/2} + δ^{−1/2}Research Paper

Ulam asked, in the early 1960s, how long the longest increasing subsequence of a random permutation typically is. The question is a test case for a whole class of problems in combinatorial probability: a quantity defined by an optimisation over exponentially many configurations (here, all subsequences) whose typical size has to be found without enumerating…

10 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability+1·Captain: mikedeng1

Subadditive Ergodic Theory 1: Kingman's Theorem — x₀ₜ/t Converges with Probability One and in Mean to a Finite ξ with E(ξ) = γResearch Paper

Many stochastic systems have an accumulated cost or passage time that grows with the length of an observation window. Splitting a window at an intermediate time gives an upper bound on the total, even when it does not give an equality. First-passage percolation and products of random matrices are examples discussed by Kingman (1973). A central question is…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 2: The 3-Partition Flow Shop on Three Machines Has a Preemptive Schedule of Finish Time 2tB Iff a 3-Partition ExistsResearch Paper

A flow shop is the simplest multi-stage production model: every job passes through the same machines in the same order, and the question is how to sequence the work so that everything is finished as early as possible. Gonzalez and Sahni's 1978 paper in Operations Research settled the computational complexity of the preemptive version of this problem, in…

8 thms3 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 1: For Rates λ(t), μ(t) ≥ 0 the Population Size Is Geometric with a Modified Zero Term, ξ_t = 1 − e^{−ρ}/W, η_t = 1 − 1/WResearch Paper

Population models often allow each individual to produce a new individual or die at rates that change over time. Seasonal conditions, exposure to an epidemic, and changing conditions in a laboratory population all make a constant rate a restrictive assumption. In Kendall's 1948 paper, the question is how the entire distribution of the population size…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+2·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VII: Bias Optimality — Four Equivalent Characterizations of a Bias Optimal Pure Stationary PolicyTextbook

A finite Markov decision problem can have several policies with the same long-run average reward even though they behave differently before reaching a recurrent class. Average reward discards a finite initial advantage: dividing total reward by the horizon sends any fixed transient contribution to zero. In applications where the process runs for a long but…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Loss Networks 3: If E e^{λX} < ∞ and 2E(X − C)⁺ < E(C − X)⁺, i.i.d. Loads on the Complete Graph Fit on Direct and Two-Edge Routes with Probability → 1Research Paper

Telephone and data networks are often fully connected at the core: every pair of switching centres has a direct trunk group, and a call that finds its direct trunk full may be alternatively routed over a two-link path through a third, tandem centre. Whether such a network can absorb fluctuations of demand without losing traffic depends on how the spare…

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

Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem 1: The Spanning-Tree Interchange Tour ψ* Is a Minimal Cost TourResearch Paper

The traveling salesman problem is NP-hard in general, so special cost structures under which it can be solved exactly in polynomial time are of lasting interest in combinatorial optimization and scheduling. One of the earliest and most cited such cases comes from sequencing on a machine whose condition is described by a single real number: a furnace…

15 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

On Tail Probabilities for Martingales 3: If E exp[−e(λ)W] ≤ e^{−λa} and E exp[−f(λ)W] ≥ e^{−λ(a+1)} for All λ ≥ 0, Then P{W < b} > ½ exp[−(½ + 2δ)a²/b]Research Paper

Freedman's inequality bounds the probability that a martingale with increments bounded above by 111 reaches a level aaa before its accumulated conditional variance exceeds bbb: the bound is exp⁡[−a2/2(a+b)]\exp[-a^2/2(a+b)]exp[−a2/2(a+b)] (D. A. Freedman, On Tail Probabilities for Martingales, Ann. Probab. 3 (1975) 100–118, Theorem (4.1), doi:10.1214/aop/1176996452). It is the standard tool…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity TheoryLinear Optimization+1·Captain: mikedeng1

The Polynomial Hierarchy and a Simple Model for Competitive Analysis: Every Optimum of the (p+1)-Level Linear Game J'(F) Is Binary, with x(F) = 1 iff the Σ_p Sentence (3.3) HoldsResearch Paper

Multi-level programs model a hierarchy of decision makers: a leader commits to a decision, a follower optimises given it, a follower of the follower optimises given both, and so on. Bilevel programs are the standard model of Stackelberg competition, toll setting, network interdiction and many other leader–follower problems in operations research (Candler…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 1: For 0 < ρ < 2r, the Modified Dual Algorithm Converges Strongly to (v*, Av*)Research Paper

Many problems in mechanics and optimal control are posed as the minimization of a convex functional of the form f(Av)−⟨b,v⟩f(Av)-\langle b,v\ranglef(Av)−⟨b,v⟩, where AAA is a differential operator and fff is non-smooth: an obstacle, a friction term, a plasticity threshold. Splitting the variable, y=Avy=Avy=Av, separates the linear operator from the non-smooth function, and a Lagrange…

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

Shock Models and Wear Processes III: The First Passage Time of a Nondecreasing Markov Wear Process Above a Fixed Level Has an IHRA DistributionResearch Paper

Reliability theory classifies life distributions by how they age. A device whose failure rate tends to increase over time is "wearing out", and the class of distributions with increasing hazard rate average (IHRA) is the one that is closed under forming coherent systems of independent components (Birnbaum, Esary and Marshall, 1966). This makes IHRA the…

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

Shock Models and Wear Processes IV: With a Random Threshold, Shock Survival Probabilities Are Submultiplicative for Every Damage Law Iff the Threshold Is NBUResearch Paper

Reliability theory classifies life distributions by how they age. A device whose remaining life, once it has survived to age ttt, is stochastically shorter than the life of a new device is called new better than used (NBU). The NBU class, together with the classes IHR (increasing hazard rate) and IHRA (increasing hazard rate average), organizes much of the…

5 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+1·Captain: mikedeng1

Linear Programming and Markov Decision Chains 3: The Representative of a Pure Stationary Policy Is an Extreme Point of the Dual LPResearch Paper

A Markov decision chain is a controlled Markov chain: in each state the controller picks an action, collects a reward and moves to a random next state with probabilities that depend on the state and the action. Under the average reward criterion, the long-run reward per step, an optimal policy can be computed by linear programming. For chains in which every…

9 thms3 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model: The Discrete-Time Proximity Process Is Dual to the Branching Process with InterferenceResearch Paper

Many models in probability, statistical physics and the theory of stochastic networks are interacting particle systems: infinitely many sites, each in state 0 or 1, each updating at random according to the states of a few other sites. A basic question about such a system is ergodicity: does it have a unique stationary distribution, and does its law converge…

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

The Relation between Customer and Time Averages in Queues: H = λG on Every Sample Path When 0 < λ < ∞, G < ∞ and Each f_n Vanishes Outside [t_n, t_n + s_n] with s_n/n → 0Research Paper

Little's law L=λWL = \lambda WL=λW says that the long-run average number of customers in a system equals the arrival rate times the average time a customer spends there. It is one of the most used identities in queueing theory, and it holds on individual sample paths under weak conditions (Little 1961; Stidham 1974). Many quantities of interest are not head counts,…

11 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Globally Convergent Inexact Newton Methods I: Inexact Newton Backtracking Converges to Every Limit Point Where F′ Is Invertible, That Point Is a Zero of F, and Initial Steps Are Eventually AcceptedResearch Paper

Newton's method for a nonlinear system F(x)=0F(x) = 0F(x)=0, with F:Rn→RnF:\mathbb R^n\to\mathbb R^nF:Rn→Rn, solves the linear system F′(xk)sk=−F(xk)F'(x_k)s_k = -F(x_k)F′(xk​)sk​=−F(xk​) at every step. For large systems that solve is itself iterative (a Krylov method such as GMRES), and it is stopped early. The resulting inexact Newton methods, introduced by Dembo, Eisenstat and Steihaug (SIAM J. Numer. Anal. 19…

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

Shock Models and Wear Processes I: Under Poisson Shocks, Cumulative Nonnegative I.I.D. Damage up to a Fixed Threshold Gives an IHRA Life DistributionResearch Paper

Reliability theory classifies life distributions by how they age. The IHRA class (increasing hazard rate average) is the smallest class of life distributions that contains the exponential distributions and is closed under forming coherent systems and taking limits in distribution (Birnbaum, Esary and Marshall 1966). It is therefore the natural class for the…

8 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Reflected Brownian Motion on an Orthant: The Skorokhod Construction Yields an Adapted, Almost Surely Unique, Time-Homogeneous Markov ProcessResearch Paper

Reflected Brownian motion on the orthant is the diffusion that arises as the heavy-traffic limit of open networks of queues. In a KKK-station network the scaled queue-length vector lives in the nonnegative orthant R+K\mathbb R^K_+R+K​; in the interior it moves like a Brownian motion, and when a station empties the process is pushed back into the orthant in a…

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

Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 3: Robust Optimal Values and Solution Sets over f-Divergence Balls Are ConsistentResearch Paper

Stochastic optimization asks for a decision xxx in a set X⊂Rd\mathcal X\subset\mathbb R^dX⊂Rd that minimises an expected loss EP0[ℓ(x;ξ)]E_{P_0}[\ell(x;\xi)]EP0​​[ℓ(x;ξ)] when the distribution P0P_0P0​ of the data ξ\xiξ is known only through a sample ξ1,…,ξn\xi_1,\dots,\xi_nξ1​,…,ξn​. The classical estimator, sample average approximation, replaces P0P_0P0​ by the empirical distribution P^n\widehat P_nPn​. Distributionally…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints 1: Under Normality, the E-Model Chance Constraints Are Equivalent to the Convex Program (29)Research Paper

Chance-constrained programming replaces a linear program max⁡c′x\max c'xmaxc′x subject to Ax≤bAx\le bAx≤b by a problem in which some data are random and each constraint only has to hold with a prescribed probability. Charnes and Cooper introduced the idea in 1959 for scheduling heating-oil production against weather-dependent demand, and the formulation is now a standard…

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

On Representatives of Subsets: Two Partitions into m Classes Have a Common System of Representatives When Any k Classes of One Meet at Least k Classes of the OtherResearch Paper

Many assignment questions reduce to one combinatorial question: given finitely many sets, can one choose a different element from each? Workers are matched to jobs they are qualified for, rows of a matrix to columns with nonzero entries. The criterion for when this is possible is Hall's marriage theorem, first stated and proved by P. Hall in a five-page…

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

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 2: The Optimal Preemptive Open Shop Makespan Equals the Largest Machine Load or Job LengthResearch Paper

Open shops model production and service systems in which every job must visit every machine, but the order of the visits is free: a car that needs an inspection, a wash and a tyre change, a patient who needs several tests, a student who sits several exams. The survey of Graham, Lawler, Lenstra and Rinnooy Kan (Ann. Discrete Math. 5, 1979) fixed the…

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

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 1: The Optimal Two-Machine Open Shop Makespan Is max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}Research Paper

Shop scheduling asks how to sequence jobs that each need processing on several machines. In an open shop, a job's operations may be executed in any order, as in testing stations, repair bays, or classroom and examination timetables, where the order in which a candidate visits the stations is irrelevant. The objective studied here is the makespan Cmax⁡C_{\max}Cmax​,…

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

Extensions of the Queueing Relations L = λW and H = λG: Under (14) and (15) the Time Average H(t) Converges if and only if the Customer Average G(s) Does, and Then H = λGResearch Paper

Queueing results often relate an average accumulated over customers to an average accumulated over time. In the familiar relation L=λWL=\lambda WL=λW, the long-run average number in a system equals the arrival rate times the average time spent there. Glynn and Whitt study a broader relation, H=λGH=\lambda GH=λG, that can represent queue lengths and waiting times but also…

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

A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management 2: Frequent Re-solving Loses at Most O(√T) Against the Deterministic LP, Uniformly in the CapacitiesResearch Paper

Network revenue management is the problem of selling several limited, perishable resources (seats on flight legs, hotel room-nights, machine hours) to customers who arrive over time and each want a fixed bundle of them. A seller who accepts every request early may run out of the resources that the most valuable later customers need, and a seller who is too…

9 thms3 active usersReviewed
PreviousPage 91 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5249500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36735482
5NINickrobbins953289156
6VEvebis25800
7FIfizzyinc321725
8SHshivm17510
9KMkmehltretter82987263
10SCShuze Chen9455324

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