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
Bandit AlgorithmsMachine Learning·Captain: Shuze Chen

Bandit Algorithms IX: Self-Normalized Concentration and Optimal DesignTextbook

Least-squares estimation from adaptively collected data is the statistical heart of linear bandits: the actions AtA_tAt​ depend on past noise, so classical fixed-design theory does not apply. Chapter 20 of Lattimore–Szepesvári resolves this with the method of mixtures: the process Mt(x)=exp⁡(⟨x,St⟩−12∥x∥Vt(λ)2)M_t(x) = \exp(\langle x, S_t\rangle - \frac{1}{2}\|x\|^2_{V_t(\lambda)})Mt​(x)=exp(⟨x,St​⟩−21​∥x∥Vt​(λ)2​) is a…

9 thms4 active usersReviewed
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
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 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
🏆Completed
Complexity TheoryLinear OptimizationOptimization·Captain: Shuze Chen

A Better-than-2 Approximation for k-MedianResearch Paper

In uncapacitated facility location (UFL) one opens a set of facilities, each at a cost, and connects every client to its nearest open facility. In k-median one opens at most kkk facilities and pays only connection costs. The two problems are linked by a Lagrangian relaxation: replacing the constraint ∣S∣≤k|S|\le k∣S∣≤k by a penalty f⋅∣S∣f\cdot|S|f⋅∣S∣ turns k-median into UFL…

25 thms3 active users
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
🏆Completed
CombinatoricsOptimizationProbability+1·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 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
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Min-Color Path with Bounded Color-DegreeResearch Paper

A robot that must move from sss to ttt through a field of obstacles, or a signal that must cross a sensor field, wants to cross as few obstacles as possible. Discretized, this is Min-Color Path: the obstacles become colors on the vertices of an arrangement graph and one asks for an sss–ttt path touching the fewest colors. The problem appears as Minimum Constraint…

26 thms3 active usersReviewed
CombinatoricsDiscrete GeometryTheoretical Computer Science·Captain: Shuze Chen

An Almost-Linear Time Algorithm for Multidimensional Subset SumResearch Paper

Subset Sum asks whether some sub-multiset of given integers sums to a target. It is one of Karp's 21 NP-complete problems, and its pseudo-polynomial complexity is a long-standing benchmark: Bellman's dynamic program runs in O(nt)O(nt)O(nt) time, Pisinger's algorithm in O(nN)O(nN)O(nN) for items bounded by NNN, and a line of work brought the bound down to O~(n+N5/3)\tilde O(n+N^{5/3})O~(n+N5/3) (Pola…

21 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

A (4m - 5)-Competitive Deterministic Algorithm for Online TransportationResearch Paper

An online transportation problem asks how to allocate arriving demand when destinations have fixed capacities and future demand is unknown. Cars arrive one at a time at points of a known finite metric space. Each car must immediately receive a garage with an unused slot. That assignment is irrevocable. The objective is the sum of the distances from arrival…

16 thms3 active usersReviewed
OptimizationProbabilityTheoretical Computer Science·Captain: Shuze Chen

A PTAS for the Minimum Sum of Radii ProblemResearch Paper

In Minimum Sum of Radii (MSR) one is given a finite metric space (P,d)(P, d)(P,d) with ∣P∣=n|P| = n∣P∣=n and an integer k∈[n]k \in [n]k∈[n], and must partition PPP into at most kkk clusters so as to minimise the sum of their radii, where the radius of a cluster CCC is rad(C)=min⁡p∈Pmax⁡q∈Cd(p,q)\mathrm{rad}(C) = \min_{p \in P} \max_{q \in C} d(p, q)rad(C)=minp∈P​maxq∈C​d(p,q). Equivalently, one covers PPP by at most kkk balls and pays the sum of…

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

Fully Dynamic Weighted Set Cover: Worst-Case Recourse and Update TimeResearch Paper

In weighted set cover, a universe of nnn elements and a family of sets with positive costs are given, and the task is a cheapest subfamily whose union covers the universe. The greedy algorithm is an O(log⁡n)O(\log n)O(logn)-approximation, and this is essentially optimal for polynomial-time algorithms. In the fully dynamic setting, elements are inserted into and deleted from…

25 thms3 active usersReviewed
Computational GeometryMachine LearningProbability+1·Captain: Shuze Chen

Dimension Reduction and Coresets for Min-Sum k-ClusteringResearch Paper

Min-sum kkk-clustering partitions a finite point set XXX into kkk clusters so as to minimise the total distance between points that share a cluster. Unlike kkk-median or kkk-means, it does not charge each point to a center, so it can recover clusters that are coherent but have no good representative point, such as two concentric rings. It is the complement of metric…

15 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Weighted Minimum Cuts and Near-Minimum Cut EstimationResearch Paper

A minimum cut of a graph with positive edge capacities is a cheapest way to disconnect it. Minimum cuts measure network reliability, and they are a basic subroutine in clustering, network design and the estimation of disconnection probabilities. A graph can have many minimum cuts: a cycle on nnn vertices has (n2)\binom n2(2n​) of them. The cactus representation of…

27 thms3 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: mikedeng1

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
PreviousPage 34 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