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

2451–2475 of 4812
Open1244Completed3568All4812
🏆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
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry+1·Captain: mikedeng1

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed: The Lattice-Point Count of an Integral Simplex Is a Short Signed Sum over Primitive ConesResearch Paper

How many integral points does a polytope contain? The question arises in integer programming, where it measures the size of a feasible set, in combinatorics, where many enumeration problems are lattice-point counts in a polytope (contingency tables, magic squares, flows), in the representation theory of Lie groups, and in the analysis of loop nests in…

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

Secretary Problems: Weights and Discounts 3: An O(log n)-Competitive Algorithm for the Discounted Secretary ProblemResearch Paper

In the secretary problem, nnn candidates with arbitrary values arrive one at a time in a uniformly random order, and an online decision maker must accept or reject each candidate on arrival, irrevocably, keeping at most one. The rule that observes the first n/en/en/e candidates and then accepts the first one better than everything seen so far selects the best…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOperations Research·Captain: mikedeng1

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 1: Pseudo-Dimension Bound from a Piecewise-Decomposable Dual ClassResearch Paper

Many algorithms in operations research and computer science have tunable parameters: sequence-alignment weights, clustering linkage interpolations, branch-and-bound branching rules, auction reserve prices. In data-driven algorithm design the parameters are chosen by optimizing average performance over a training set of problem instances drawn from an…

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

Sequencing with Earliness and Tardiness Penalties: With Due-Date Tolerances, the Least Optimal Common Due Date Puts One Job at an End of Its Tolerance WindowResearch Paper

Earliness/tardiness (E/T) scheduling penalizes a job both for finishing late and for finishing early. It models just-in-time production, where an early job ties up inventory and a late one delays a customer. Baker and Scudder's review (Oper. Res. 38 (1990) 22–36) organized the single-machine E/T literature around a short list of structural properties of…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

A Polylogarithmic-Competitive Algorithm for the k-Server Problem: Randomized k-Server Is O(log² k · log³ n · log log n)-Competitive on Every n-Point MetricResearch Paper

The k-server problem (Manasse, McGeoch and Sleator, 1990) is the central problem of online computation: kkk servers sit on points of a metric space, requests arrive one at a time at points of the space, and each request must be served by moving a server to it, at a cost equal to the distance travelled. An online algorithm decides without knowing future…

16 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning+1·Captain: mikedeng1

Reinforcement Learning: An Introduction VI: Batch TD(0) Converges to the Certainty-Equivalence EstimateTextbook

Temporal-difference (TD) learning estimates the value of each state of a Markov reward process from observed experience, updating an estimate toward a target built from the next reward and the current estimate of the next state. Monte Carlo (MC) methods instead update toward the full observed return. Both are standard prediction methods in reinforcement…

9 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 2: An Iterated-Logarithm Upper Bound for Weighted Conditionally Sub-Gaussian Martingale DifferencesResearch Paper

The law of the iterated logarithm (LIL) gives the exact almost-sure size of the fluctuations of a sum of random variables. For independent fair ±1\pm1±1 increments x1,x2,…x_1,x_2,\dotsx1​,x2​,… with partial sums SnS_nSn​, Khinchin (1924) showed that lim sup⁡n∣Sn∣/2nlog⁡log⁡n=1\limsup_n |S_n|/\sqrt{2n\log\log n}=1limsupn​∣Sn​∣/2nloglogn​=1 almost surely; Kolmogorov (1929) extended this to bounded independent increments, and Hartman…

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

Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time: Delayed SWPT Has Competitive Ratio 2Research Paper

A single machine must process nnn jobs that arrive over time. Job jjj is released at time rjr_jrj​, needs pjp_jpj​ units of uninterrupted processing, and has weight wj>0w_j > 0wj​>0; the goal is to minimize the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​. Offline, with all release dates equal to zero, Smith's rule (sequence by nondecreasing pj/wjp_j/w_jpj​/wj​) is optimal (Smith 1956);…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Correlated Equilibrium as an Expression of Bayesian Rationality I: Bayes Rationality at Every State Yields Exactly the Correlated Equilibrium DistributionsResearch Paper

Nash equilibrium is the standard solution concept for strategic games, but it is usually justified by appeal to what players "would" do once they somehow coordinate on a profile. Correlated equilibrium, introduced by Aumann (J. Math. Econ. 1, 1974), enlarges the set of outcomes by letting players condition their actions on correlated private signals. In Corr…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOptimization+1·Captain: mikedeng1

Reinforcement Learning: An Introduction III: The Policy Improvement Theorem and Policy IterationTextbook

Reinforcement learning methods search for good behaviour by alternating two activities: estimating how good the current behaviour is, and changing the behaviour in the direction those estimates suggest. Sutton and Barto call this pattern generalized policy iteration and use it as the organizing idea of their textbook (Sutton & Barto 2018, §4.6). Its…

9 thms3 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisMachine Learning·Captain: mikedeng1

Theory of Reproducing Kernels III: The Product of Two Reproducing Kernels Is the Kernel of the Diagonal Restrictions of the Direct ProductResearch Paper

A reproducing kernel is the function K(x,y)K(x,y)K(x,y) that represents point evaluation in a Hilbert space of functions: f(y)=(f,K(⋅,y))f(y) = (f, K(\cdot, y))f(y)=(f,K(⋅,y)). Kernels are combined all the time. In machine learning, a kernel on pairs of objects is routinely built as the pointwise product of two simpler kernels, and in complex analysis the product ∣K(x,y)∣2=K(x,y)K(y,x)|K(x,y)|^2 = K(x,y)K(y,x)∣K(x,y)∣2=K(x,y)K(y,x) of a…

9 thms3 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisMachine Learning·Captain: mikedeng1

Theory of Reproducing Kernels I: The Sum of Two Reproducing Kernels Is the Kernel of the Sum Class with the Minimal-Decomposition NormResearch Paper

Reproducing kernel Hilbert spaces are Hilbert spaces of functions in which evaluation at a point is a continuous linear functional. They appear wherever a space of functions carries a natural quadratic norm: Bergman and Hardy spaces of analytic functions, spaces of harmonic functions and solutions of elliptic equations, Sobolev spaces in one dimension, and,…

8 thms3 active usersReviewed
Control TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Optimal Electricity Demand Response Contracting with Responsiveness Incentives 2: The Producer's First-Best Value in Closed FormResearch Paper

Electricity demand response asks consumers to lower their consumption during price events, when generation is expensive or scarce. Field trials such as the Low Carbon London experiment showed that consumers do react to price signals, but that the reaction is erratic: the average consumption falls while its variability stays high, and a producer that has to…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningMarkov Chain+1·Captain: mikedeng1

Reinforcement Learning: An Introduction II: The Bellman Optimality Equation and the Existence of an Optimal PolicyTextbook

Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) is the standard introductory text of the field. Its Chapter 3 sets up the model that the rest of Part I works in: the finite Markov decision process (MDP), the value functions of a policy, and the Bellman equations that relate the value of a state to the values of its…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics+1·Captain: mikedeng1

Fundamentals of Queueing Theory VIII: Lindley's Integral Equation for the G/G/1 QueueTextbook

The single-server queue with general interarrival times and general service times, written G/G/1 in Kendall's notation, is the model left when every distributional assumption is removed from the classical single-server queue. Customers arrive one at a time, wait in line in first-come, first-served order, and are served one at a time. Almost nothing about it…

12 thms3 active usersReviewed
PreviousPage 99 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR37035540
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821002265
10SCShuze Chen9455327

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