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
🏆Completed
CombinatoricsOptimizationProbability+1·Captain: mikedeng1

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 2: Randomized Double Greedy Achieves 1/2 of the Optimum in ExpectationResearch Paper

Many selection problems assign a value to each subset of a finite collection: the coverage supplied by chosen facilities, the influence reached by chosen seeds, or the value of a coalition. A submodular set function has diminishing returns in the precise sense that the combined value of two sets, counting their overlap once, does not exceed the sum of their…

11 thms3 active usersReviewed
🏆Completed
Dynamical SystemsProbabilityStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 4: Subgaussian Martingale Noise with Σ exp(−c/γ_n) < ∞ for Every c > 0 Satisfies Assumption A1 Almost SurelyResearch Paper

A stochastic approximation algorithm is a recursion

10 thms3 active usersReviewed
🏆Completed
AnalysisDynamic ProgrammingOptimization+2·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VI: Lower Semianalytic Functions — Analytically Measurable ε-Optimal Selectors (Jankov–von Neumann)Textbook

Dynamic programming over uncountable state and control spaces needs two things at every stage: the optimal cost-to-go, obtained by minimizing over the control, must be a function that can be integrated against the next stage's transition probabilities, and a policy that nearly attains the minimum must be measurable, so that it defines a stochastic process.…

8 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations 1: Revenue Sharing at w = φc Coordinates the Channel and Gives the Retailer the Share φ of Its Optimal ProfitResearch Paper

A supplier who sells to an independent retailer through a plain per-unit wholesale price faces double marginalization: the retailer orders less than the quantity that maximizes the profit of the supply chain as a whole, because each unit costs him the wholesale price rather than the production cost. Supply chain contracting studies payment schemes under…

10 thms3 active usersReviewed
🏆Completed
AnalysisDynamic ProgrammingOptimization+2·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case V: Semicontinuous Functions — a Borel-Measurable Minimizing Selector for Lower Semicontinuous CostsTextbook

Every step of the dynamic programming algorithm on a general state space does three things: it takes a conditional expectation of the cost-to-go under a transition kernel, it minimizes the resulting function of state and control over the control, and, if a policy is to be produced, it picks a control for each state that attains or nearly attains that…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

The Price of Stability for Network Design with Fair Cost Allocation I: The Price of Stability of Fair Cost Sharing Is at Most H(k), and This Is TightResearch Paper

Many networks are built and paid for by the users they serve: multicast trees, virtual overlays, shared subnetworks of the Internet. A protocol proposes a design and a rule for splitting its cost, and each participant is free to accept the proposal or defect to a cheaper alternative. The designer therefore cannot impose the global optimum; the best it can…

11 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic SystemsTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Stochastic Inventory Control Models 2: The Triple-Balancing Policy Costs at Most Three Times the Optimum for Stochastic Lot-SizingResearch Paper

Periodic-review inventory control with a fixed ordering cost is one of the oldest problems in operations research. A firm reviews its stock at the beginning of each of TTT periods, decides whether to place an order, pays a fixed cost KKK for every order it places, and pays holding costs on leftover stock and penalties on unmet (backlogged) demand. When demand…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 2: The Three-Colorable Addition-Multiplication Gadget Has Error Amplification 81Research Paper

Nash's theorem guarantees that every finite game has a mixed equilibrium, but says nothing about how hard one is to find. Daskalakis, Goldberg and Papadimitriou (SIAM J. Comput. 39(1), 2009) showed that computing a Nash equilibrium is complete for the class PPAD of total search problems whose solutions are guaranteed by a parity argument on a directed graph…

15 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

One-Machine Sequencing to Minimize Certain Functions of Job Tardiness II: EDD Order Minimizes Any Sum of Convex Nondecreasing Tardiness Penalties When No Job Starts After Its Due DateResearch Paper

A single machine must process a set of jobs, each with a processing time and a due date, and the cost of a schedule depends on how late the jobs finish. Total tardiness is the classical criterion, but in many applications lateness is penalised more than proportionally: a job one week late costs more than twice a job half a week late, and a quadratic or…

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

Secretary Problems: Weights and Discounts 5: A 3e-Competitive Algorithm for the Graphic Matroid Secretary ProblemResearch Paper

In the secretary problem, nnn items with nonnegative values arrive one at a time in a uniformly random order, and an online algorithm must decide on each arrival, irrevocably, whether to keep it. The classical version keeps one item; the rule that observes a 1/e1/e1/e fraction of the arrivals and then takes the first item better than everything seen picks the best…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov Chain·Captain: mikedeng1

Discrete Dynamic Programming 2: A Stationary Policy Is Nearly Optimal as the Discount Factor Tends to 1 Exactly When It Maximizes x(g) and, Among Those, y(g)Research Paper

A finite Markov decision problem with discounting is solved by Howard's policy improvement routine: start from a stationary policy, switch to actions that do better against its value, repeat. When the discount factor β\betaβ tends to 111 the total discounted income typically diverges, and the natural targets become the long-run average income and, among…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex Optimization·Captain: mikedeng1

Consensus of Subjective Probabilities: The Pari-Mutuel Method: Equilibrium Track Probabilities Exist and Are UniqueResearch Paper

A group of mmm individuals each hold a subjective probability distribution over the same nnn outcomes, and one wants a single distribution representing their consensus. Averaging and convolution are the obvious candidates. Eisenberg and Gale (Ann. Math. Statist. 30(1), 1959) observe that a real institution already performs such an aggregation: the pari-mutuel…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov Chain·Captain: mikedeng1

Discrete Dynamic Programming 1: Every Finite Markov Decision Problem Has a Stationary Policy That Is Optimal for All Discount Factors Sufficiently Near 1Research Paper

A Markov decision problem models a system that is observed once per period and controlled by choosing an action: the action earns an immediate income and determines the probabilities of the next state. Inventory control, machine replacement, queue admission and many reinforcement-learning benchmarks are of this form. With future income discounted by a…

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

The Price of Anarchy of Finite Congestion Games II: For Symmetric Games the Average Social Cost Price of Anarchy Is (5N-2)/(2N+1)Research Paper

Selfish routing and resource sharing are modelled by congestion games: each player picks a set of shared resources, and the cost of a resource grows with the number of players using it. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures how much worse the social cost of a worst Nash equilibrium is than the optimum. For…

9 thms3 active usersReviewed
🏆Completed
Dynamical SystemsProbabilityStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 6: An Attractor Whose Basin Meets the Attainable Set Contains the Limit Set with Positive ProbabilityResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing step sizes γn\gamma_nγn​ and a noise term Un+1U_{n+1}Un+1​. Recursions of this form appear in stochastic gradient methods, adaptive control, learning in games (fictitious play, reinforcement learning) and urn models. The ODE method compares the iterates…

11 thms3 active usersReviewed
🏆Completed
Dynamical SystemsProbabilityStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 3: Martingale Noise with Bounded q-th Moments and Summable γ_n^(1+q/2) Satisfies Assumption A1 Almost SurelyResearch Paper

A stochastic approximation algorithm is a recursion

10 thms3 active usersReviewed
🏆Completed
Dynamical SystemsStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 5: If V(Λ) Has Empty Interior for a Lyapunov Function V, Every Internally Chain Transitive Set Lies in ΛResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing steps γn\gamma_nγn​ and noise UnU_nUn​. Stochastic gradient descent, the Robbins–Monro procedure, reinforcement-learning updates and learning dynamics in games all have this form. The ODE method compares such a recursion with the deterministic dynamics …

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainProbability·Captain: mikedeng1

An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion: With Finite Storage a Modified Base-Stock Policy Is Strongly Average-Cost OptimalResearch Paper

A manufacturer that makes one product to stock faces random demand, can produce at most bbb units per period, and can store at most UUU units. The classical result without the production limit is that a base-stock policy is optimal: raise inventory to a fixed level yˉ\bar yyˉ​ each period. With a production limit, the natural modification is to produce up to yˉ\bar yyˉ​ w…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationReinforcement Learning·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 1: The Robust Value Function Is the Optimum of a Policy- and Value-Regularized Convex ProgramResearch Paper

A Markov decision process (MDP) is solved for one model of its dynamics and rewards, but in practice that model is estimated from data, and a policy that is optimal for the estimate can perform poorly on the true system (Mannor et al., 2007). Robust MDPs address this by evaluating a policy against the worst model in an uncertainty set U\mathcal UU (Iyengar,…

8 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Open Queueing Networks in Heavy Traffic: Reflected Brownian Motion Limit for the Queue Length ProcessResearch Paper

Open networks of single-server queues with general interarrival and service distributions are the standard model of job shops, communication networks and service systems. Outside the product-form (Jackson) case their queue-length distributions are not known in closed form. When every station is close to saturation, a heavy-traffic limit replaces the network…

18 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Quantifying the Bullwhip Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and Information 1: Centralizing Demand Information Does Not Eliminate the Bullwhip EffectResearch Paper

The bullwhip effect is the observation that the variability of orders increases as one moves up a supply chain, from the retailer towards the manufacturer and its suppliers. It was documented in industry and in classroom experiments such as the Beer Game (Sterman 1989), and analysed by Lee, Padmanabhan and Whang (1997), who named demand forecasting, lead…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryDiscrete Geometry+1·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
OptimizationTheoretical 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
OptimizationStochastic 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 DesignProbability·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
PreviousPage 58 of 106Next

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