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
Convex OptimizationProbability·Captain: mikedeng1

Data-Driven Robust Optimization I: An Uncertainty Set Whose Support Function Dominates Value at Risk Implies a Probabilistic Guarantee for Every Concave ConstraintResearch Paper

Robust optimization replaces an uncertain constraint f(u~,x)≤0f(\tilde{\mathbf u},\mathbf x)\le 0f(u~,x)≤0, whose parameter u~∈Rd\tilde{\mathbf u}\in\mathbb R^du~∈Rd is random, by the requirement that the constraint hold for every u\mathbf uu in a chosen uncertainty set U\mathcal UU:

12 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization III: The Best Affine Policy Can Cost More Than m^(1/2−δ)/4 Times the Fully Adaptable OptimumResearch Paper

Two-stage adaptive optimization models decisions taken in two steps: a first-stage decision xxx is fixed before an uncertain right-hand side bbb is revealed, and a second-stage recourse y(b)y(b)y(b) is chosen afterwards, with the worst case over an uncertainty set U\mathcal UU to be minimized. The fully-adaptable problem, in which yyy may be an arbitrary function of bbb, is…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Deriving Robust Counterparts of Nonlinear Uncertain Inequalities: For a Regular Nominal Vector, a Concave Uncertain Constraint Holds Robustly iff Its Fenchel Counterpart (FRC) Is SolvableResearch Paper

In robust optimization, a decision must satisfy a constraint for every parameter value in a prescribed uncertainty set. A nonlinear uncertain constraint can be difficult to use directly because it contains a universal condition over a continuum of parameters. Ben-Tal, den Hertog, and Vial study constraints whose value is concave in the uncertain parameter.…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization II: With m + 3 Extreme Points the Best Affine Policy Can Cost More Than (2 − δ) Times the OptimumResearch Paper

Two-stage adaptive optimization models decisions made in two steps: a first-stage decision is fixed before an uncertain parameter is revealed, and a second-stage (recourse) decision may then depend on the realized value. In the robust version, the uncertain parameter ranges over an uncertainty set and the objective is the worst-case cost. Such models arise…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization I: An Affine Policy Is Optimal When the Uncertainty Set Is a SimplexResearch Paper

Two-stage adaptive optimization models decisions taken in two rounds: a first-stage decision xxx is fixed before an uncertain parameter is revealed, and a second-stage decision y(b)y(b)y(b) is chosen after the parameter bbb is observed, so that the second stage may depend on bbb arbitrarily. The objective is the worst case over an uncertainty set U\mathcal UU of possible…

7 thms4 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

The Big Data Newsvendor: Practical Insights from Machine Learning: The L2-Regularized Feature-Based Newsvendor Rule Generalizes with a Bound Free of the Number of FeaturesResearch Paper

The newsvendor problem is the basic model of inventory under uncertain demand. A decision maker orders qqq units before demand DDD is observed, and pays a unit backordering cost bbb for each unit of unmet demand and a unit holding cost hhh for each unit left over. When the demand distribution is known, the optimal order is a quantile of it. In practice the…

13 thms4 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

On the Stochastic Matrices Associated with Certain Queuing Processes 2: The GI/M/1 Imbedded Chain Is Ergodic iff ρ < 1 and Recurrent iff ρ ≤ 1Research Paper

A single-server queue in which customers arrive according to a renewal process and are served in exponentially distributed times is the system GI/M/1. Observed just before successive arrivals, its queue length is a Markov chain on {0,1,2,… }\{0, 1, 2, \dots\}{0,1,2,…}, the imbedded chain introduced by D. G. Kendall (Kendall 1953, Ann. Math. Statist. 24, pp. 338–354). Whether…

12 thms4 active usersReviewed
Control TheoryDynamic ProgrammingProbability+1·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VIII: The Infinite-Horizon Borel Models — the Optimality Equation J* = T(J*) under (P), (N), (D)Textbook

Infinite horizon dynamic programming asks for the least expected cost of controlling a stochastic system forever, and for a policy attaining it. On finite or countable state spaces the theory has been classical since Bellman, Blackwell (1965) and Strauch (1966). Many models in operations research, inventory control, queueing and economics have continuous…

23 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization+1·Captain: mikedeng1

Maximal Flow Through a Network II: In an ab-Planar Network Some Chain from Source to Sink Meets Every Cut Exactly OnceResearch Paper

The maximum flow problem asks how much of a commodity can be shipped from a source to a sink through a network whose arcs have limited capacities. L. R. Ford, Jr. and D. R. Fulkerson's 1956 paper Maximal Flow Through a Network proved the minimal cut theorem: the largest flow value equals the smallest total capacity of a set of arcs that separates source…

10 thms4 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

Reversibility and Stochastic Networks VII: Clustering Processes — Poisson Product-Form Equilibrium of the Open Clustering ProcessTextbook

Many systems consist of units that form themselves into clusters: individuals at a gathering forming conversational groups, monomers forming polymers, particles coagulating and fragmenting. Chapter 8 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) treats such clustering processes as Markov processes whose state counts the clusters of…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Maximization of a Linear Function of Variables Subject to Linear Inequalities: Under Nondegeneracy the Simplex Technique Ends in Infeasibility, Unboundedness, or a Maximum Feasible SolutionResearch Paper

Linear programming asks for the best value of a linear objective under linear constraints. In the form studied by George B. Dantzig in 1951, all variables are nonnegative and the constraints are equalities. The simplex technique moves between small sets of columns, seeking a feasible vector first and then improving its objective. Its basic promise is…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 3: Trimming an Approximate Nash Equilibrium Yields a Well-Supported OneResearch Paper

The complexity of computing a Nash equilibrium is usually studied for an approximate equilibrium, because an exact equilibrium of a game with three or more players can require irrational probabilities. Two approximation notions are in use, and results proved for one do not automatically transfer to the other. Daskalakis, Goldberg and Papadimitriou (SIAM J.…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games V: The Mixed Price of Anarchy of the Average Social Cost Is at Most (3+sqrt 5)/2Research Paper

When many self-interested users share resources whose cost grows with use (links of a network, servers, machines), each user picks the option that is cheapest for them given what the others do, and the resulting equilibrium can be worse for the group than a centrally planned allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS…

7 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Analysis of Thompson Sampling for the Multi-armed Bandit Problem 2: Logarithmic Regret for N ArmsResearch Paper

Thompson Sampling is the oldest heuristic for the multi-armed bandit problem: proposed by Thompson in 1933, it plays each arm with the posterior probability that the arm is the best one. It is simple to implement, performs well empirically (Chapelle and Li, NIPS 2011), and has been used in production systems such as click-through-rate prediction for search…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: mikedeng1

Maximal Flow Through a Network I: The Minimal Cut Theorem — the Maximal Flow Value Equals the Minimum Value of a Disconnecting SetResearch Paper

The question behind this mission was posed by T. E. Harris to L. R. Ford, Jr. and D. R. Fulkerson at RAND, in the setting of rail transport: given a rail network linking two cities, with a capacity on every link, find the largest steady flow from one city to the other. Ford and Fulkerson's answer, the minimal cut theorem, published in the Canadian Journal…

13 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Maximum Matching and a Polyhedron With 0,1-Vertices: The Vertices of the Matching Polyhedron Are Exactly the Matching VectorsResearch Paper

A matching in a graph is a set of edges no two of which share a node. Given a real weight on every edge, the maximum-weight matching problem asks for a matching of largest total weight. It is one of the basic problems of combinatorial optimization: assignment, pairing and scheduling problems reduce to it, and it is the standard example of a combinatorial…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

On the Douglas–Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators: Generalized Douglas–Rachford Splitting Converges Weakly if A+B Has a Zero, Else Is UnboundedResearch Paper

Many problems in convex optimization, variational inequalities and equilibrium modelling reduce to finding a point xxx with 0∈Ax+Bx0 \in A x + B x0∈Ax+Bx, where AAA and BBB are maximal monotone operators on a real Hilbert space H\mathcal HH: for example, minimizing f+gf + gf+g for closed proper convex f,gf, gf,g is the case A=∂fA = \partial fA=∂f, B=∂gB = \partial gB=∂g. When the resolvent of A+BA + BA+B is hard…

18 thms4 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOptimization+1·Captain: mikedeng1

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time 1: The Expected Shadow of a Gaussian-Perturbed Polytope Has Polynomially Many VerticesResearch Paper

The simplex method solves linear programs very fast in practice, yet for most pivot rules there are inputs on which it takes exponentially many steps (Klee and Minty, 1972, for Dantzig's rule; Goldfarb, 1983, for the shadow-vertex rule). Average-case analyses (Borgwardt, 1980s; Smale, 1983) explained good behaviour on random inputs, but random inputs look…

31 thms4 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

The Strong Perfect Graph Theorem I: A Graph Is Perfect If and Only If It Is BergeResearch Paper

A perfect graph is one whose coloring problem has a particularly sharp answer on every induced subgraph: the fewest colors needed is exactly the size of its largest clique. This makes a local obstruction, a clique, certify the optimum number of colors throughout the graph. Claude Berge proposed in 1961 that perfection could be recognized by the absence of…

22 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsMechanism Design+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 2: Sequential Posted Prices e/(e−1)-Approximate the Optimal Revenue under a Partition Matroid ConstraintResearch Paper

A seller who knows the distributions of buyers' values can maximise expected revenue with Myerson's optimal mechanism (Myerson 1981): collect bids, compute virtual values, serve a feasible set of maximum virtual surplus, and charge threshold payments. Real sellers seldom run such auctions. They post prices: a buyer is offered a take-it-or-leave-it price and…

21 thms4 active users
🏆Completed
Algorithmic Game TheoryCombinatoricsMechanism Design+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 1: Sequential Posted Prices 2-Approximate the Optimal Revenue under a Matroid ConstraintResearch Paper

A seller who must decide whom to serve among several buyers with private values can, in principle, run Myerson's revenue-optimal mechanism: collect bids, compute virtual values, serve the feasible set of largest virtual surplus, and charge threshold payments (Myerson 1981). In practice sellers rarely do this. Retail, ticketing and online platforms mostly…

21 thms4 active users
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain·Captain: mikedeng1

On Sequential Decisions and Markov Chains 2: Under Irreducibility, an Optimal Solution of a Linear Program over State-Action Frequencies Yields an Optimal Stationary ProcedureResearch Paper

A Markov decision problem asks how to control a system that moves at random between finitely many states, where each decision changes the probabilities of the next move and incurs a cost. Cyrus Derman's 1962 paper On Sequential Decisions and Markov Chains (Management Science 9(1):16–24) treats two criteria: the long-run average cost per period, and the total…

11 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov Chain·Captain: mikedeng1

On Sequential Decisions and Markov Chains 1: Deterministic Stationary Procedures Are Optimal for the Long-Run Average Cost and for the Total Cost to AbsorptionResearch Paper

A Markov decision process with finitely many states and decisions is the basic model of sequential decision making under uncertainty: inventory replacement, machine maintenance, queue control and pursuit problems all fit it. Its computational methods (Howard's policy iteration, 1960; Manne's linear programming formulation, 1960) search only over stationary p…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 1: Approximate Fixed Points of Nash's Map Are Approximate Nash EquilibriaResearch Paper

A finite game describes several decision makers whose payoffs depend on everyone's choices. A Nash equilibrium is a collection of choices at which no single player can improve their expected payoff by changing strategy alone. Equilibrium existence is a classical result, but a computational argument needs to connect an object that can be approximated…

7 thms4 active usersReviewed
🏆Completed
OptimizationStochastic Systems·Captain: mikedeng1

A Characterization of Waiting Time Performance Realizable by Single-Server Queues: The Conservation-Law Polytope Is the Convex Hull of the Preemptive Priority VectorsResearch Paper

A single server shared by several classes of jobs must decide, at every moment, which class to serve. Different scheduling rules give different mean response times to the classes, and a system designer often starts from the other end: a target vector of mean response times, one per class, and the question whether any rule can meet it. Coffman and Mitrani…

32 thms4 active users
PreviousPage 28 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