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
CombinatoricsTheoretical Computer Science·Captain: iris

Precedence Constraint Scheduling on a Fixed Number of MachinesResearch Paper

Scheduling unit-time jobs under precedence constraints on a fixed number of identical machines, written Pm∣prec,pj=1∣Cmax⁡Pm\mid prec, p_j=1\mid C_{\max}Pm∣prec,pj​=1∣Cmax​, is a long-standing question of scheduling theory (surveys: Lawler–Lenstra–Rinnooy Kan–Shmoys 1993, Mnich–van Bevern 2018). For m=1m=1m=1 the problem is immediate, and for m=2m=2m=2 it is solved in polynomial time. When the number of…

29 thms3 active usersReviewed
Complexity TheoryProbability·Captain: iris

Stochastic Load Balancing with Strict Machine-Reservation BudgetsResearch Paper

In stochastic load balancing jobs with random sizes must be placed on machines so that the expected maximum load, the makespan, is small. In many systems (cloud slots, replicated storage, network paths) each job must commit to a small set of machines before its size is known, and may later be moved only inside that set. Alemán Espinosa, Garg, Ibrahimpur,…

74 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Canada RetravelledResearch Paper

Shortest paths with uncertain edge lengths are a basic model of routing under incomplete information. In the Stochastic Canadian Traveller Problem (CTP), introduced by Papadimitriou and Yannakakis in 1991, a traveller must get from sss to ttt in a graph whose edge lengths are independent random variables with known distributions. The length of an edge becomes…

28 thms3 active usersReviewed
CombinatoricsOptimizationTheoretical Computer Science·Captain: iris

Approximate Covering and Packing in PolymatroidsResearch Paper

Covering a ground set by few independent sets is a classical problem in combinatorial optimization. For a single matroid, the matroid union theorem of Edmonds and Fulkerson gives the minimum number of independent sets needed to cover EEE as max⁡S⌈∣S∣/r(S)⌉\max_S \lceil |S|/r(S)\rceilmaxS​⌈∣S∣/r(S)⌉, with polynomial-time algorithms. For the intersection of d≥2d \ge 2d≥2 matroids, covering by…

33 thms3 active usersReviewed
EconomicsMachine Learning·Captain: iris

Maximizing Unobserved Welfare: Logarithmic Regret from PurchasesResearch Paper

A seller who produces goods and posts prices to a stream of buyers usually wants revenue. A planner who runs a public market, such as a food bank, a cooperative or a platform with a welfare mandate, wants something else: the total utility of the buyers minus the cost of production. The difficulty is that utility is never observed. The seller sees only what…

25 thms3 active usersReviewed
CombinatoricsComplexity TheoryOptimization·Captain: iris

A Constructive FPT Algorithm for Integer Cone Optimization with Convex CostsResearch Paper

Many packing, covering and scheduling problems ask how a collection of locally feasible objects can be combined into a global solution. A bin configuration, the load of one machine, or one allocation of resources is a generator. A nonnegative integer multiplicity records how often it is used, and the sum of the chosen generators must satisfy global…

30 thms3 active usersReviewed
Complexity TheoryDiscrete GeometryOptimization·Captain: iris

High-Multiplicity Bin Packing is FPTResearch Paper

Bin packing asks whether given items fit into a given number of bins of a fixed capacity. In the high-multiplicity version there are only ddd different item sizes, and each size comes with the number of items of that size. Instances of this kind arise in cutting-stock problems and in scheduling identical jobs on identical machines, where very many items share…

19 thms3 active usersReviewed
Dynamic ProgrammingStochastic SystemsTheoretical Computer Science·Captain: iris

Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers: A Deterministic Quasi-Polynomial-Time Algorithm Computes a (1−ϵ)(1-\epsilon)(1−ϵ)-Optimal Adaptive Service PolicyResearch Paper

Providing timely service under high capacity utilization is a central issue in stochastic systems, and customer impatience has major economic consequences in data centers, healthcare, ride-hailing and call centers (Wang, Li, Jiang, 2010). Cygan, Englert, Gupta, Mucha and Sankowski (ITCS 2013) introduced one of the structurally simplest models of it: a…

24 thms3 active usersReviewed
Control TheoryProbabilityStochastic Systems·Captain: iris

The Exact Online Threshold for the Asymmetric Binary PerceptronResearch Paper

The asymmetric binary perceptron (ABP) is a random constraint satisfaction problem. Given a matrix G∈RM×NG\in\mathbb R^{M\times N}G∈RM×N with independent standard Gaussian entries and a margin κ∈R\kappa\in\mathbb Rκ∈R, one asks for a sign vector σ∈{±1}N\sigma\in\{\pm1\}^Nσ∈{±1}N with Gσ/N≥κ1MG\sigma/\sqrt N\ge\kappa\mathbf 1_MGσ/N​≥κ1M​ coordinatewise. When M/N→αM/N\to\alphaM/N→α, the largest density at which a…

36 thms3 active usersReviewed
Dynamic ProgrammingOptimization·Captain: iris

Performance Guarantees for Network Revenue Management with Flexible Products: The Approximate Policy Earns at Least a 1/(1+θL)1/(1 + \theta L)1/(1+θL) Fraction of the Optimal Expected RevenueResearch Paper

Network revenue management sells the limited capacities of resources to demand that arrives over time, in air travel, hospitality, media advertising and cloud computing. A flexible product can be served by several combinations of resources, and the service provider chooses which. Airlines sell discount tickets for an origin-destination pair without fixing…

25 thms3 active usersReviewed
Algorithmic Game TheoryProbabilityTheoretical Computer Science·Captain: iris

Adwords with Unknown Budgets and Beyond: Generalized Perturbed Greedy, Blind to Budgets, Is 0.522/(1+γ)0.522/(1+\gamma)0.522/(1+γ)-Competitive at β=1.15\beta = 1.15β=1.15 and 0.508/(1+γ)0.508/(1+\gamma)0.508/(1+γ)-Competitive at β=1\beta = 1β=1Research Paper

In Adwords (Mehta, Saberi, Vazirani and Vazirani, 2007, doi), a platform has advertisers with budgets. Queries arrive one at a time, advertisers bid on each query, and the platform shows at most one ad immediately and irrevocably. The winner pays their bid, up to their remaining budget, and the goal is to maximize the total budget used, against an arbitrary…

22 thms3 active usersReviewed
Convex OptimizationOptimization·Captain: iris

Silver Rate Is (Almost) Optimal for Gradient DescentResearch Paper

Gradient descent (GD) with a predetermined stepsize schedule H=(h1,…,hn)H=(h_1,\dots,h_n)H=(h1​,…,hn​) is the method xt=xt−1−ht∇f(xt−1)x_t=x_{t-1}-h_t\nabla f(x_{t-1})xt​=xt−1​−ht​∇f(xt−1​), 1≤t≤n1\le t\le n1≤t≤n, with the stepsizes fixed before the run. With the constant stepsize 1/L1/L1/L it converges at rate O(n−1)O(n^{-1})O(n−1) on convex LLL-smooth functions, and the classical lower bound Ω(n−2)\Omega(n^{-2})Ω(n−2) of Nemirovsky and Yudin holds for every…

33 thms3 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: iris

Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management: The K-Ring's Matching Loss Is at Most 3n/(d+1)·q^((d+1)/3)Research Paper

In middle-mile parcel transportation, a carrier decides in advance which pairs of stations may share a truck route; on a given day only some stations have enough residual demand to need one, and the routes actually used pair up these active stations. Allowing every pair is the most flexible design but the hardest to operate, so the question is how few…

20 thms3 active usersReviewed
Algorithmic Game TheoryMechanism DesignProbability·Captain: iris

On the Power of Determinism in Multi-Item AuctionsResearch Paper

A seller with mmm items faces one buyer whose values for the items are private and drawn from a known distribution. The revenue-optimal mechanism for a single item is a posted price (Myerson 1981). For two or more items the optimal mechanism can require lotteries, an infinite menu, and can be non-monotone in the value distribution (Hart and Reny 2015), so the…

23 thms3 active usersReviewed
Dynamic ProgrammingProbability·Captain: iris

Distributionally Robust Markov Decision Processes and Their Connection to Risk Measures: Robust Value Iteration and Deterministic Markov Optimal Policies for Both Players on Borel SpacesResearch Paper

A Markov decision process assumes that the law of the random disturbances is known. In inventory, energy and finance models that law is estimated, and a controller who is averse to the estimation error wants a policy that performs well under every law in a set of plausible ones. This is distributionally robust control. Bäuerle and Glauner's paper Distributio…

33 thms3 active usersReviewed
Dynamic ProgrammingOptimizationRevenue Management and Pricing·Captain: iris

Dynamic Pricing with Menu Costs: Approximation Schemes and Applications to Grocery Retail: A Budget-Feasible Pricing Strategy Within 1 − ε of Optimal in Time (|I|/ε · ϱmax)^O(T) · ‖U¹‖∞^O(1)Research Paper

Grocery retailers set prices on a weekly calendar, but every price change has a cost: shelf labels must be reprinted and replaced, systems updated, staff scheduled. The economics literature calls these menu costs; for large US supermarket chains they were measured at a sizeable fraction of net margins (Levy, Bergen, Dutta, Venable, 1997), so retailers limit…

21 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance VI: With Proportional Transaction Costs the Optimal Portfolio Has Buy, Hold and Sell Regions Given by ConesTextbook

In frictionless discrete-time portfolio models the investor rebalances freely, and with a homogeneous utility the optimal policy keeps a constant fraction of wealth in the stock. Real trading is costly: every purchase or sale of stock pays a fee proportional to the traded amount. A constant-fraction policy then trades every period and pays the fee every…

34 thms3 active usersReviewed
Dynamic ProgrammingLinear OptimizationOptimization·Captain: iris

Markov Decision Processes with Applications to Finance XII: The Primal and Dual Linear Programs of a Contracting Markov Decision Problem Have Equal Values and Optimal SolutionsTextbook

A discounted Markov Decision Problem asks for a policy that maximizes the expected discounted sum of rewards of a controlled Markov chain. Besides value iteration and policy iteration, the third classical way to compute such policies is linear programming: the value function is the smallest function satisfying a family of linear inequalities, and the dual…

18 thms3 active usersReviewed
Dynamic ProgrammingOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance XIV: When the One-Step Stopping Set Is Closed the One-Step-Look-Ahead Rule Is OptimalTextbook

Optimal stopping asks when to end a random process so as to maximize the expected reward. It covers house selling, the secretary problem, sequential testing and the exercise of American options. Chapter 10 of N. Bäuerle and U. Rieder, Markov Decision Processes with Applications to Finance (Springer, 2011, doi:10.1007/978-3-642-18324-9) treats these problems…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamic ProgrammingOptimization·Captain: iris

Markov Decision Processes with Applications to Finance II: In Convex Markov Decision Models the Convex Functions in Bb+\mathbb{B}_b^+Bb+​ Satisfy the Structure AssumptionTextbook

In a finite-horizon Markov decision problem the value functions VnV_nVn​ are computed backwards by the Bellman equation Vn=TnVn+1V_n = T_nV_{n+1}Vn​=Tn​Vn+1​. Bäuerle and Rieder (Springer 2011) organize the general theory around one hypothesis, the Structure Assumption (SAN)(\mathrm{SA}_N)(SAN​): if a class of functions IMn\mathbb{IM}_nIMn​ is stable under the maximal reward operator TnT_nTn​ and every…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingProbabilityTheoretical Computer Science·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms3 active usersReviewed
OptimizationProbability·Captain: iris

Dynamic Pricing and Capacity Optimization in Railways: the static-price flexible-capacity policy has an O(κ)O(\sqrt{\kappa})O(κ​) optimality gap and is asymptotically optimalResearch Paper

National railways sell tickets for a given travel day over a long sales horizon. Many of them sell two products at once: a reserved ticket, tied to a seat on one train, and an unreserved ticket, which lets the passenger board any train on the travel day and stand if no seat is free. The operator also decides how many coaches of each kind a train carries.…

15 thms3 active usersReviewed
Convex OptimizationOptimizationTheoretical Computer Science·Captain: iris

Batching and Optimal Multi-stage Bipartite Allocations: PR-MWM Is (1 − (1 − 1/K)^K)-Competitive for K-Stage Fractional Vertex-Weighted MatchingResearch Paper

Matching platforms rarely decide on one request at a time. A ride-hailing marketplace clears requests in short windows, an ad exchange serves a video session's slots together, and cloud and retail systems process demand in rounds. Between the fully offline problem and the online model of Karp, Vazirani and Vazirani (STOC 1990) lies a question with an…

18 thms3 active usersReviewed
Control TheoryDynamic ProgrammingStochastic Systems·Captain: iris

Condition-Based Production for Stochastically Deteriorating Systems: Optimal Policies and Learning: The Optimal Production Rate Decreases in Deterioration, Time to Maintenance and Base RateResearch Paper

Production systems such as wind turbines and assembly equipment can often be run faster or slower, and running faster usually wears them out faster. Between scheduled maintenance visits, an operator can therefore trade revenue now against deterioration later. Condition-based production, a term coined by Uit het Broek et al. (2020), makes this trade-off…

16 thms3 active usersReviewed
Convex OptimizationOptimizationProbability·Captain: iris

Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management: Explicit Global Convergence Bound for Mirror Stochastic GradientResearch Paper

Many operations management models choose a decision xxx whose effect is filtered through randomness: a booking limit xxx is truncated by random demand ξ\xiξ, so the realized sales are x∧ξx\wedge\xix∧ξ; an order quantity is scaled by a random yield. The resulting stochastic program

25 thms3 active usersReviewed
PreviousPage 36 of 145Next

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