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,679 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

Open935Completed2679All3614
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Worst-Case Conditional Value-at-Risk with Application to Robust Portfolio Management 2: For a Compact Convex Set of Discrete Distributions, Worst-Case CVaR Equals min_α max_π G_β(x, α, π)Research Paper

Conditional value-at-risk (CVaR) is the standard coherent measure of tail risk in portfolio selection and risk-averse optimization: for a confidence level β\betaβ it is, roughly, the expected loss in the worst (1−β)(1-\beta)(1−β) fraction of outcomes. Its practical appeal comes from the representation of Rockafellar and Uryasev (2000, 2002), which writes CVaR as the…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Worst-Case Conditional Value-at-Risk with Application to Robust Portfolio Management 1: Under Mixture Distribution Uncertainty, Worst-Case CVaR Equals the Minimum over α of max_i F^i_β(x, α)Research Paper

Conditional value-at-risk (CVaR) is the standard coherent measure of tail risk in portfolio selection, insurance and stochastic programming. Its practical appeal comes from a variational formula of Rockafellar and Uryasev (J. Risk 2000; J. Banking Finance 2002): CVaR at level β\betaβ is the minimum over a scalar α\alphaα of a convex function, so that minimizing…

11 thms2 active usersReviewed
🏆Completed
AnalysisProbabilityStochastic Systems·Captain: mikedeng1

Some Useful Functions for Functional Limit Theorems 2: Addition, Supremum and the Reflecting Barrier Preserve J₁ Convergence of Linearly Centered PathsResearch Paper

Queueing models often represent work arriving to and leaving a server by a real-valued input path. The resulting workload cannot fall below a barrier. Functional limit theorems describe what happens to such paths under scaling, but a limit for the input path is useful only when it can be carried through the workload transformation. Ward Whitt’s 1980 paper…

9 thms2 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: mikedeng1

A Scheduling Model for Reduced CPU Energy: For P(s) = s², the Average Rate Heuristic Has Competitive Ratio Between 4 and 8Research Paper

A processor can save energy by running slowly when work is light, but a deadline may force it to run faster. Yao, Demers, and Shenker formulated this tradeoff as an offline and online scheduling problem for a variable-speed processor in their 1995 FOCS paper. Their Average Rate Heuristic (AVR) uses only each job's arrival, deadline, and required work to set…

19 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov Chain·Captain: mikedeng1

Discrete Dynamic Programming with Sensitive Discount Optimality Criteria 2: No Improvement of Order n+1 Implies n-Discount Optimality, Which Rules Out Improvement of Order nResearch Paper

A finite Markov decision process is usually solved under one of two criteria: the expected total discounted reward, for a fixed interest rate, or the long-run average reward. Neither is satisfactory when the interest rate is small and not known precisely. Blackwell (Blackwell 1962) showed that some stationary policy is optimal for every discount factor…

17 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Bounded Rationality in Newsvendor Models I: Under Uniform Demand the Logit Newsvendor's Order Is Truncated Normal and Its Mean Is Pulled from x* Toward the MidpointResearch Paper

The newsvendor problem is the basic single-period inventory model: a decision maker orders xxx units at unit cost ccc before a random demand DDD is observed, sells min⁡(D,x)\min(D, x)min(D,x) units at price ppp, and loses unsold units. Its optimal order is the critical fractile x∗=F−1(1−c/p)x^* = F^{-1}(1 - c/p)x∗=F−1(1−c/p) of the demand distribution FFF. Laboratory experiments show that human subjects do…

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

Understanding the Efficiency of Multi-Server Service Systems II: In the M/M/s Queue with (1 − ρ)√s = γ, the Wait of a Delayed Customer Is Exponential with Mean 1/(γ√s)Research Paper

A service system with several servers can use a larger fraction of its capacity than a single-server system while still giving customers an acceptable wait. The design question is how much unused capacity is needed as the number of servers grows. Ward Whitt's study begins with a factory manager deciding whether to put four machines in one work area. It uses…

4 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Some Theoretical Aspects of Road Traffic Research III: Minimum Average Journey Time on Alternative Routes — Equal Marginal Times ε and the Closed Forms (32)–(33)Research Paper

J. G. Wardrop's 1952 paper Some theoretical aspects of road traffic research (DOI 10.1680/ipeds.1952.11259) introduced the two criteria that still organise traffic assignment. When a flow of traffic can choose between several routes from one origin to one destination, the paper (p. 345) considers two ways the traffic might divide:

8 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 1: Iterative Rounding Finds a Spanning Tree of Cost at Most the LP Optimum with Every Degree at Most B_v + 1Research Paper

A network designer may need a cheap connection that keeps the number of links at each site within a local capacity. The minimum bounded-degree spanning tree problem asks for the cheapest spanning tree of a weighted, undirected graph whose vertex degrees respect prescribed upper bounds. The capacity constraints matter in settings where a low-cost tree alone…

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

The G/GI/N Queue in the Halfin–Whitt Regime 3: The Number in a Non-Idling G/GI/N System Satisfies the Infinite-Server System Equation (2.8)Research Paper

A many-server queue has NNN identical servers, a stream of arriving customers, and a buffer in which customers wait when every server is busy. It models call centres, hospital wards and server farms, and the regime of practical interest is the Halfin–Whitt or quality-and-efficiency-driven regime, in which the number of servers NNN grows with the arrival rate …

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Incentive Compatibility and the Bargaining Problem II: Every Equilibrium of Every Choice Mechanism Yields an Incentive-Feasible Allocation, F** = F*Research Paper

An arbitrator who must choose among collective options for a group of players usually does not know the players' private characteristics. The arbitrator can only ask, and a player who expects to profit from a false answer may give one. Before designing any procedure, the arbitrator therefore needs to know which expected-payoff allocations can be reached at…

6 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Regenerative Stochastic Processes 2: The Ergodic Theorem — a Cumulative Process Satisfies w_t/t → κ₁/μ₁ with Probability OneResearch Paper

Many quantities in operations research accumulate over time in a system that periodically starts afresh: the cost incurred by an inventory system that returns to the same stock level, the work completed by a server between successive moments it empties, the reward collected by a machine between repairs. The basic question about such a quantity is its…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryAnalysisProbability·Captain: mikedeng1

Values of Large Games II: Oceanic Games 2: Oceanic Values Are Limits of Values of Finite Weighted Majority GamesResearch Paper

Weighted voting models assign a coalition a win when its combined vote reaches a quota. The Shapley value measures a player's contribution by averaging the change it makes when added to every possible predecessor coalition. This is straightforward to define for a finite list of voters, but a voting body may contain a few major holders and a very large…

8 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

On the Relationship Between Inventory Costs and Variety Benefits in Retail Assortments I: An Optimal Assortment Always Consists of the k Most Popular Variants for Some kResearch Paper

A retailer deciding which variants of a product to carry (colors, sizes, flavors) trades the extra sales that variety brings against the inventory cost of stocking many low-volume items. van Ryzin and Mahajan (Management Science 45(11), 1999) gave the first model that couples a multinomial logit (MNL) choice model of consumer substitution with newsvendor…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: mikedeng1

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 5: Full-Batch LPT Is Within 4/3 − 1/(3m) of the Optimal Makespan on Parallel Batch MachinesResearch Paper

Burn-in is the final reliability test of integrated circuits: boards loaded with chips are held in an oven at elevated temperature for a minimum specified time, so that marginal devices fail before shipment. An oven holds several boards at once, and a load may stay in the oven longer than its specification but never shorter. Lee, Uzsoy and Martin-Vega (Oper.…

10 thms2 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

The Weighted Majority Algorithm 1: WM Makes at Most log(w_init/w_fin)/log(2/(1+β)) Mistakes on Any SequenceResearch Paper

In online prediction, a learner makes a forecast before seeing the next label. A collection of other forecasters may offer useful advice, but the learner need not know beforehand which forecaster will perform well. Littlestone and Warmuth's Weighted Majority Algorithm (WM) gives a deterministic way to combine such advice. Its guarantees hold for every…

4 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 3: Dynamic Program DP3 Minimizes the Number of Tardy Equal-Length Jobs on a Batch Machine with Agreeable Release and Due DatesResearch Paper

Semiconductor burn-in tests hold several jobs in an oven at once. A production planner must decide which jobs share each oven run and in what order those runs take place. A job may become available only after earlier manufacturing steps, and a due date marks when its test should finish. The planning objective here is to minimize how many jobs finish after…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: mikedeng1

Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 2: Branch and Bound with the Two-Machine Lower Bound Finds a Sequence of Least Mean Completion TimeResearch Paper

In a two-machine flow shop, each of nnn jobs is processed first on machine AAA and then on machine BBB, and the order of the jobs is to be chosen. For the makespan (the finishing time of the last job), Johnson (1954) gave an exact sorting rule. For the sum (equivalently, the mean) of the completion times, no such rule is known: the problem is NP-hard in the…

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 6: When Workers Are Alike in Production, Gross Substitutes Is Equivalent to Nonincreasing Returns to WorkersResearch Paper

Kelso and Crawford's 1982 Econometrica paper studies a labor market in which firms hire sets of heterogeneous workers at individually negotiated salaries. Their existence results for the core and for competitive equilibrium, and the convergence of their salary-adjustment process, all rest on one hypothesis about each firm's technology, the gross-substitutes…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Monotone Comparative Statics I: The Argmax Is Monotone Nondecreasing in (t, S) If and Only If f Is Quasisupermodular in x and Has the Single Crossing Property in (x; t)Research Paper

An optimization problem often changes when a parameter changes: a price rises, a constraint expands, or a strategic environment shifts. Comparative statics asks whether the optimal choice moves in a predictable direction. The usual numerical tools, such as derivatives, can be unavailable when choices form a discrete set or the objective is neither smooth…

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Potential Games 1: A Game Is an Exact Potential Game If and Only If I(γ, u) = 0 on Every Simple Closed Path of Length 4Research Paper

In a strategic game, each player evaluates a change in their own strategy using that player's own payoff. These incentives need not point in a common direction. A potential game is a case in which one real-valued function records every player's payoff change under a unilateral deviation. This common function lets questions about incentives be expressed as…

10 thms2 active usersReviewed
🏆Completed
Control TheoryStochastic Systems·Captain: mikedeng1

Distributed Scheduling Based on Due Dates and Buffer Priorities 2: Under Last Buffer First Serve the Number of Parts Stays Bounded, Eventually by (λc(ε)+γ)/(1−ρ−λε)Research Paper

Semiconductor wafer fabrication lines are reentrant: a wafer returns to the same photolithography or etching station many times along its route, so the parts competing for a machine are at different stages of completion. In such a line, a local dispatching rule decides at every machine which waiting part goes next, and the question is whether a given rule…

10 thms2 active usersReviewed
🏆Completed
Control TheoryStochastic Systems·Captain: mikedeng1

Distributed Scheduling Based on Due Dates and Buffer Priorities 1: First Buffer First Serve Is Stable on Every Nonacyclic Flow Line Whose Bursty Arrival Rate Is Below CapacityResearch Paper

Semiconductor wafer fabs are the standard example of a reentrant manufacturing line: a wafer visits the same lithography or etching station many times along a route of hundreds of steps, so each station holds parts at many different stages of completion and must decide, every time a machine frees up, which of them to serve next. Kumar (Re-entrant lines,…

7 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Monte Carlo Bounding Techniques for Determining Solution Quality in Stochastic Programs: The Expected Sample-Average Optimal Value Is a Lower Bound on z* That Improves with Sample SizeResearch Paper

Most stochastic programs that arise in practice, such as two-stage stochastic linear programs with recourse, have far too many scenarios to be solved exactly. The standard remedy is sample-average approximation: draw nnn independent observations of the random data, replace the expectation by the sample mean, and solve the resulting deterministic problem. A…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 3: The Partition Job Shop on Two Machines Has a Schedule of Finish Time 5T, Preemptive or Not, Iff a Partition ExistsResearch Paper

A job shop is the basic model of a factory floor in which every job follows its own route through the machines. Minimizing the time at which the last job is finished (the finish time, or makespan) is one of the central problems of deterministic scheduling theory, and the question of which special cases admit efficient algorithms has organized much of the…

11 thms2 active usersReviewed
PreviousPage 92 of 108Next

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