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
Algorithmic Game TheoryAnalysis·Captain: iris

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games: Polynomial Games of Degree d With No α-PNE for Any α < α(d), Where α(d) ≥ √d/(2 ln d) for Large dResearch Paper

Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…

28 thms4 active usersReviewed
CombinatoricsGraph Theory·Captain: iris

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k: Cut-Sets of Value OPT_k-cut Are Recovered by Every Minimum (S, T)-Terminal Cut for Some |S|, |T| ≤ 2k − 1Research Paper

Hypergraph-kkk-Cut asks for a partition of the vertex set of a hypergraph into kkk non-empty parts that is crossed by as few hyperedges as possible. It models clustering and partitioning tasks in which an interaction involves more than two objects (VLSI netlists, multi-way relations in data). For graphs, the number of optimum kkk-partitions is polynomial for…

25 thms4 active usersReviewed
Actuarial ScienceEconomicsProbability·Captain: iris

An Unexpected Stochastic Dominance: Pareto Distributions, Dependence, and Diversification: A Weighted Average of Negatively Associated Super-Pareto Losses Stochastically Dominates a Single LossResearch Paper

Diversification is the default advice of risk management: spreading a unit of exposure over several independent losses reduces risk. For losses with finite mean this is true in a strong sense: if X1,…,XnX_1,\dots,X_nX1​,…,Xn​ are identically distributed with finite mean, the weighted average ∑iθiXi\sum_i\theta_iX_i∑i​θi​Xi​ can never be larger than a single X1X_1X1​ in first-order stochastic…

20 thms4 active usersReviewed
Captain: Shuze Chen

Dynamic Stochastic Matching Under Limited Time: Constant-factor reward approximation on arbitrary and bipartite graphsResearch Paper

A matching platform must decide whether to pair available agents now or wait for a more valuable partner. Waiting creates an opportunity and a risk: an agent may leave before that partner arrives. Ride sharing, service exchanges and matching markets motivate models in which arrivals continue indefinitely and departure times are not announced in advance. A…

23 thms4 active usersReviewed
Probability·Captain: iris

Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem: The Expected k-TSP Length Among n Uniform Points Is Θ((k−1)·n^(−(1+1/(k−1))/2)) for All 2 ≤ k ≤ nResearch Paper

The kkk-traveling salesman problem (kkk-TSP) asks for the shortest path through some kkk of nnn given points, with the choice of points left to the optimizer. It models routing with selective service, where a vehicle serves only part of its demand, and it is a building block of approximation algorithms for the traveling repairman problem. For the full tour, the…

17 thms4 active usersReviewed
Machine LearningProbability·Captain: iris

Marrying Stochastic Gradient Descent with Bandits: Learning Algorithms for Inventory Systems with Fixed Costs: the (δ,S) learning algorithm has regret O(log N √N) over N epochsResearch Paper

Periodic-review inventory control with a fixed ordering cost is a basic model of operations management: every order costs K>0K>0K>0 regardless of its size, so a firm orders in batches and the optimal policy is an (s,S)(s,S)(s,S) policy rather than a base-stock level (Scarf 1960; Zheng 1991). In practice the demand distribution is unknown and, when unmet demand is lost,…

41 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: iris

Investment Efforts Under Complementary Sourcing: The Role of Market Risk and Endogenous Pricing: market risk reverses the first-mover disadvantage when rµ ≥ 3ϵ0 + σ and σ/ϵ0 ≤ 3 − 2√2Research Paper

In complementary sourcing, a product's value depends on the efforts of both a supplier and a manufacturer, and each firm's effort raises the marginal value of the other's. Chip lithography is a standard example: an equipment maker and a chip maker each invest heavily, and neither investment pays without the other. When firms invest in sequence, the…

30 thms4 active usersReviewed
Dynamic ProgrammingProbability·Captain: iris

Asymptotically Optimal Lagrangian Policies for Multi-Warehouse, Multi-Store Systems with Lost Sales: the SLaBS policy's expected loss is O(√(min{M,N}·T·N·log(TN)))Research Paper

Retailers with many stores often hold a finite stock of a product in a few distribution centres and ship it to the stores over a selling season, with no replenishment of the centres themselves: seasonal goods, fashion, end-of-life products. Unmet store demand is lost. The decision is how much to send to each store in each period, from which warehouse,…

29 thms4 active usersReviewed
ProbabilityStochastic Systems·Captain: iris

Appointment Scheduling for Multiple Servers: the phase-type recursion gives the exact waiting-time and makespan laws and the cost of every schedule of the D/PH/s appointment systemResearch Paper

An appointment schedule fixes in advance when each of nnn clients should arrive for a service of random length. Clinics, MRI suites, legal counselling and visa offices all use one, and the schedule trades off clients' waiting time against the idle time and overtime of the servers. Pooling physicians or machines so that any client can be served by any of sss serv…

46 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOptimization·Captain: iris

Zero-Sum Games and Linear Programming Duality: Every Max-Min Strategy of Dantzig's Game with One Extra Row Yields Optimal LP Solutions or Certifies That No Optimal Solution ExistsResearch Paper

Linear programming duality and the minimax theorem for zero-sum games are two faces of the same convexity fact. The classical direction, from LP duality to the minimax theorem, is textbook material: the optimal strategies of a matrix game are the optimal solutions of a pair of dual LPs. The converse direction, solving an LP by solving a game, goes back to Da…

23 thms4 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: Shuze Chen

Pacing Equilibrium in First Price Auction Markets: Existence, uniqueness, and revenue maximization of first price pacing equilibriaResearch Paper

An advertiser buying many impressions must decide how to distribute a limited budget across auctions. Bidding the full value in every auction can exhaust the budget before all opportunities have been considered. A pacing multiplier scales an advertiser's bids by one common factor. The resulting allocation depends on other advertisers' multipliers as well as…

15 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: Shuze Chen

Online Matching and Ad Allocation: MSVV attains the optimal small-bids competitive ratioResearch Paper

An advertising platform must decide which advertiser receives each arriving opportunity before it knows what will arrive later. A bidder offering a high payment now may also be the only bidder interested in a later request. Spending that bidder’s budget immediately can therefore reduce the total money collected over the day. This tension is the Adwords…

16 thms4 active usersReviewed
ProbabilityStatistics·Captain: Shuze Chen

Distributionally Robust Conditional Quantile Prediction with Fixed Design: Concentration of the surrogate residual distributionResearch Paper

A conditional quantile describes a level of a response that is exceeded with a specified probability after its explanatory variables are fixed. Such predictions enter inventory decisions when demand depends on prices, promotions, or product characteristics. These explanatory variables may be designed or selected deliberately. Treating their historical…

20 thms4 active usersReviewed
Captain: Shuze Chen

Perishable Inventory Theory: A Review: Convex costs and age-sensitive optimal orderingResearch Paper

Perishability makes inventory age matter. Two warehouses with the same total stock can face different expiration risks and choose different replenishments. Nahmias’ 1982 review collects structural results for these decisions and contrasts fixed shelf lives with random lifetimes and proportional decay.

37 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: Shuze Chen

College Admissions and the Stability of Marriage: Applicant optimality of deferred acceptanceResearch Paper

College admissions involves decisions on both sides of a capacity-constrained market. An applicant may prefer one college while that college prefers another applicant. An offer can be declined, and a waiting-list place can become available after another offer has already been accepted. Gale and Shapley formulate an assignment problem in which the inputs are…

5 thms4 active usersReviewed
Dynamic ProgrammingOptimizationProbability·Captain: Shuze Chen

Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality: Asymptotic optimality of feasible dynamic fluid policiesResearch Paper

Many sequential allocation problems combine numerous individually small projects with a common capacity constraint. A firm may allocate capital across investments, inventory across locations, or service opportunities across competing activities. Each local decision changes future rewards and local states. At the same time, a common observed signal can…

22 thms4 active usersReviewed
Convex OptimizationMachine LearningStatistics·Captain: Shuze Chen

Shape-Constrained Regression Using Sum of Squares Polynomials: Almost-sure consistency of convex sum-of-squares estimatorsResearch Paper

Regression estimates an unknown relationship between features and responses from noisy observations. In many applications, a qualitative property of that relationship is known before data are collected. A production response may exhibit convexity, or a response may have a known directional derivative bound. Enforcing such information throughout a continuous…

18 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: Shuze Chen

Robust Assortment Optimization Under the Markov Chain Choice Model: Min-max duality and optimal robust assortmentsResearch Paper

A retailer chooses which products to offer before learning exactly how customers will substitute between them. A product that looks attractive under estimated demand can perform poorly when those estimates are wrong. Robust assortment optimization evaluates each offer set by its worst expected revenue over a specified set of possible customer models. The…

14 thms4 active usersReviewed
OptimizationProbability·Captain: Shuze Chen

Pandora’s Box Problem with Order Constraints: Optimal threshold search on treesResearch Paper

A searcher comparing possible hires, research directions, or other alternatives may have to pay to learn each alternative's value. Only the best inspected alternative is eventually selected, while every inspection cost is paid. When access to one alternative requires investigating another first, a locally unattractive inspection may unlock a valuable…

12 thms4 active usersReviewed
Optimization·Captain: Shuze Chen

Assortment Planning for Recommendations at Checkout Under Inventory Constraints: Quarter-competitive online recommendations with polynomial runtimeResearch Paper

A recommendation at checkout can earn immediate revenue while consuming inventory that would have made later recommendations possible. A customer shopping for a table may also buy chairs, but a later customer who wanted those chairs as her primary purchase may leave if they have sold out. The decision therefore affects both direct sales and future…

20 thms4 active usersReviewed
Bandit AlgorithmsProbability·Captain: Shuze Chen

Matching While Learning: Asymptotically optimal regret for decentralized matchingResearch Paper

A service platform may know which kinds of jobs are available while still learning the abilities of new workers. An assignment then has two effects: it produces a reward and supplies information that can improve later assignments. Limited job supply couples these decisions across workers. Sending one worker to a useful learning task consumes capacity that…

16 thms4 active usersReviewed
Machine LearningProbability·Captain: Shuze Chen

Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand: Nearly square-root regret for SALAResearch Paper

A retailer choosing both a price and an inventory target faces two coupled decisions. A higher price changes customer demand, while a smaller inventory target hides demand that exceeds available stock. The retailer observes sales, but cannot count customers who leave empty-handed. This makes even the realized lost-sales penalty unavailable as a learning…

15 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: Shuze Chen

Minimum Label s-t Cut has Large Integrality Gaps: Nearly cube-root integrality gap for the strengthened relaxationResearch Paper

A network failure can remove several connections at once. When the connections share a physical resource, paying for or disabling that resource acts on an entire class of edges. The minimum label s-t cut problem captures this distinction: edges carry labels, and the cost of removing a label is paid once, regardless of how many edges have that label. Zhang…

14 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingProbabilityStochastic Systems·Captain: Shuze Chen

Markov Decision Processes (Puterman) VIII: Average Optimality for Semi-Markov ModelsTextbook

A controller may make decisions whenever a machine fails, a customer arrives, or a service finishes. The time between two decisions then depends on the state and the chosen action. Counting decisions alone does not measure elapsed operating time: a policy earning a large reward per decision may spend so long between decisions that its reward per unit time…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: Shuze Chen

Production Planning by Mixed Integer Programming IV: An Extended Formulation for the Mixing SetTextbook

Mixed-integer production models combine quantities that vary continuously with decisions counted in whole units. A relaxation that allows the latter quantities to be fractional can admit points excluded by every implementable plan. The convex hull of the original feasible set describes the strongest convex relaxation in the same variables. Understanding…

9 thms4 active usersReviewed
PreviousPage 16 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