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

Stochastic Machine Scheduling with Precedence Constraints 2: LP-Based Graham List Scheduling Is a (2 − 1/m + max{1, (m − 1)Δ/m})-Approximation for P|in-forest|E[Σ w_j C_j]Research Paper

Scheduling jobs whose durations are uncertain is the normal situation in project management, manufacturing and computing: a job's processing time becomes known only when the job finishes, but a distribution for it is available in advance. Stochastic machine scheduling models this by random, independent processing times PjP_jPj​ and asks for a scheduling policy,…

11 thms4 active usersReviewed
Convex OptimizationOptimization·Captain: mikedeng1

Primal-Dual Interior-Point Methods for Self-Scaled Cones I: After One Short Step from N(β), λ₂(x₊, s₊) ≤ (2 + δ − κ)(ϵ + κ)²/((1 − δ)²(1 − κ)³)Research Paper

Linear programming, second-order cone programming and semidefinite programming are all instances of conic linear programming: minimize a linear function over the intersection of an affine subspace with a closed convex cone. Primal-dual interior-point methods solve these problems in polynomially many iterations and are the algorithms behind most conic…

17 thms4 active usersReviewed
Convex OptimizationMarkov ChainStochastic Systems·Captain: mikedeng1

An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand: Adaptive(α, β) Has Per-Period Regret O(N(L)^(−1/3)) at α = β = 1/2Research Paper

Periodic-review inventory systems with lost sales and a positive replenishment lead time are a basic model of retail and spare-parts operations: demand that cannot be met from stock is lost, and an order placed today arrives τ\tauτ periods later. Even with a known demand distribution the optimal policy depends on the whole vector of outstanding orders and is…

12 thms4 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

An Introduction to Timetabling 2: When Every Teacher Is Available in at Most Two Periods, Limited Backtracking Finds a Timetable or Correctly Reports That None ExistsResearch Paper

School and university timetabling is one of the oldest applications of combinatorial optimization. In the class–teacher model, classes and teachers must be brought together for a prescribed number of lectures, each lecture occupies one period, and nobody can be in two places at once. With no further side constraints the model reduces to edge colouring of a…

16 thms4 active users
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
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
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

The Matroids with the Max-Flow Min-Cut Property: Binary Mengerian Clutters and the Q6 MinorResearch Paper

Several classical theorems of combinatorial optimization say that a family of sets arising from a graph packs: the maximum number of pairwise disjoint members equals the minimum size of a set meeting every member. König's theorem on bipartite graphs, Menger's theorem, the max-flow min-cut theorem of Ford and Fulkerson, Edmonds' branching theorem and the…

30 thms4 active usersReviewed
Linear OptimizationOptimization·Captain: Shuze Chen

Disjunctive Programming IX: The Correspondence Between Lift-and-Project Cuts and Simple Disjunctive CutsTextbook

Chapter 6 built lift-and-project (L&P) cuts from a cut-generating LP, and Chapter 7 surveyed alternative nonlinear constructions reaching the same integer hull. This chapter asks a sharper question: how do L&P cuts relate, coefficient for coefficient, to older, more classical cutting planes — simple disjunctive cuts and mixed integer Gomory cuts, derived…

14 thms4 active users
ProbabilityStatisticsStochastic Systems·Captain: mikedeng1

Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms: Langevin Diffusion Limit of the First CoordinateResearch Paper

The random walk Metropolis algorithm is one of the most widely used Markov chain Monte Carlo methods for sampling from a density known up to a constant. Its one tuning parameter is the variance of the Gaussian proposal. If the variance is too small, the chain accepts almost every move but barely moves. If it is too large, it proposes long jumps that are…

15 thms4 active usersReviewed
CombinatoricsComplexity TheoryOptimization+1·Captain: mikedeng1

A Threshold of ln n for Approximating Set Cover II: The Inapproximability of Max k-CoverResearch Paper

Max kkk-cover is the basic coverage problem of combinatorial optimization. The input is a collection of subsets of a finite ground set and a number kkk; the task is to choose kkk subsets that together cover as many points as possible. It models facility and sensor placement, the selection of a small committee or feature set representing a population, and budgeted…

23 thms4 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

A Threshold of ln n for Approximating Set Cover I: The ln n Inapproximability of Set CoverResearch Paper

Set cover is the problem of covering a finite ground set with as few members of a given family of subsets as possible. It models facility location, crew scheduling, test-suite minimization and many other selection problems in operations research, and it is one of the canonical NP-hard problems. The greedy algorithm, which repeatedly picks the subset…

20 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Stochastic Linear Optimization under Bandit Feedback 1: The Regret Bound of ConfidenceBallResearch Paper

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a decision xtx_txt​ from a fixed set D⊆RnD\subseteq\mathbb R^nD⊆Rn and observes only the noisy cost of that one decision, whose expectation is a fixed but unknown linear function μ⊤xt\mu^\top x_tμ⊤xt​. The model covers online routing, ad and product selection with feature vectors, and any…

24 thms4 active users
Dynamic ProgrammingOptimizationTheoretical Computer Science·Captain: mikedeng1

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy JobsResearch Paper

A production planner may have many jobs competing for a small number of identical machines. Each job has a processing requirement, a due date and a penalty for missing that date. Minimizing the sum of those penalties is the weighted tardy jobs problem. Its numerical parameters matter for exact optimization: a dynamic program can depend on the largest due…

18 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Faster Approximation Schemes for Scheduling on Related MachinesResearch Paper

In makespan minimization on uniformly related machines, Qm∥Cmax⁡Qm\|C_{\max}Qm∥Cmax​, each of nnn jobs is assigned to one of mmm machines that differ only in speed, and the goal is to minimize the time at which the most loaded machine finishes. The problem is strongly NP-hard when mmm is part of the input, already for identical machines (Garey–Johnson 1978), so a fully…

28 thms3 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted GraphsResearch Paper

All-pairs approximate shortest paths (APASP) asks for a matrix ddd with δ(u,v)≤d[u,v]≤α δ(u,v)+β\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)+\betaδ(u,v)≤d[u,v]≤αδ(u,v)+β for every pair of vertices. Static algorithms trade the stretch (α,β)(\alpha,\beta)(α,β) against running time; the classical additive tradeoffs are due to Dor, Halperin and Zwick for unweighted graphs and to Cohen and Zwick for weighted graphs,…

17 thms3 active usersReviewed
Computational ComplexityComputational GeometryTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Makespan and Parameterized Hardness for Multi-Robot Motion PlanningResearch Paper

Moving several robots through a shared workspace without collisions is a basic problem of robotics and computational geometry. Deciding whether one arrangement of robots can be transformed into another is PSPACE-hard when the number of robots is part of the input, so attention turns to a small number kkk of robots. Known algorithms for kkk square robots in a…

25 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Structural Complexity of Matching with IndifferencesResearch Paper

Centralized school choice and other two-sided assignment systems are run by clearinghouses that announce a single outcome. When preferences contain ties (a student may be indifferent between several schools), the classical notion of stability splits into weak, strong and super stability (Irving 1994), and a deterministic rule must also say which stable…

19 thms3 active usersReviewed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

A Unified Framework for Parameterized Approximation of Clustering Objectives via Distance MappingsResearch Paper

Center-based clustering asks for kkk centers in a metric space that serve a finite set of data points well. The classical objectives (k-median, k-means, k-center, min-sum of radii) and their variants with fault tolerance, capacities, penalties or outliers have mostly been studied one at a time, each with its own algorithm. In structured metrics (bounded…

16 thms3 active usersReviewed
CombinatoricsGraph TheoryLinear algebra+1·Captain: Shuze Chen

Breaking the Quadratic Time Barrier for Flow Sparsifiers via Schur Complement LocalizationResearch Paper

Many multicommodity flow and cut problems only concern a small set of terminals inside a large network. Vertex sparsification replaces the network by a graph on the terminals alone that preserves, up to a factor called the quality, how well every pattern of terminal traffic can be routed. Such a graph is a preprocessing step for approximation algorithms…

19 thms3 active usersReviewed
Algorithmic Game TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Efficient Equilibrium Computation in Colonel Blotto GamesResearch Paper

The Colonel Blotto game (Borel, 1921) is the basic model of competitive resource allocation: two players divide fixed budgets among several contests, and each contest goes to the larger allocation. It models military and security planning, elections and R&D races. In the continuous version, allocations are arbitrary nonnegative reals, so each player has a…

29 thms3 active usersReviewed
OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Contention Resolution from SamplesResearch Paper

A contention resolution scheme receives a random collection of available elements and selects a feasible subset. With a capacity of kkk, feasibility means selecting at most kkk elements. The input can respect capacity on average while exceeding it on particular realizations. A useful selection rule must resolve these conflicts while preserving a guarantee for…

40 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsComplexity Theory·Captain: mikedeng1

Learning and Optimisation of Rank Ordered Gain Functions and with Modular CostsResearch Paper

A principal choosing a group of workers must compare the group's collective value with the cost of engaging its members. Individual competencies give useful ordering information, but a ranking alone does not describe how participation costs interact with collective performance. Etesami, Liu and Sahitaj study this distinction through augmented rank-ordered…

26 thms3 active usersReviewed
Discrete GeometryProbability·Captain: iris

Separating Measures by HyperplanesResearch Paper

Given red and blue points in Rd\mathbb R^dRd, join every red point to every blue point by a segment and weigh each segment by its length under a fixed norm. What fraction of the total weight can a single affine hyperplane always cut, counting a segment when its endpoints lie strictly on opposite sides? Correa, Griesbach, Harb, Hommelsheim, Jlibene, Livanos and…

26 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Minimum Sum-of-Radii Clustering with Strong and Weak OraclesResearch Paper

In the minimum sum of radii problem (MSR), nnn points of a metric space must be covered by at most kkk balls centred at input points, and the objective is the sum of the radii. Unlike kkk-center, which charges only the largest radius, MSR rewards making every cluster as tight as possible. With exact distances, polynomial-time approximation factors improved from …

32 thms3 active usersReviewed
Algorithmic Game TheoryEconomicsMechanism Design+1·Captain: Shuze Chen

On the Power and Limitations of Multiple Intermediaries for Single-Item AuctionsResearch Paper

A seller may be unable to receive buyers' bids directly. Intermediaries can control access to its auction and charge bidders for the right to participate. Competition between those intermediaries might reduce exclusion, but it need not transfer their revenue back to the seller. These are different questions: whether the item reaches the buyer who values it…

16 thms3 active usersReviewed
PreviousPage 7 of 39Next

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