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
Graph TheoryLinear OptimizationOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VIII: A Vertex Schedule Maximizes the Net Present Value iff Its Spanning-Tree Subprojects Have the Right SignsTextbook

Long-running projects such as construction, plant engineering or software development involve payments to and from the contractor at many points in time: disbursements when activities are carried out, progress payments when milestones are reached. When the planning horizon is long, money received later is worth less, and the natural financial objective is…

9 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

One-Machine Sequencing to Minimize Certain Functions of Job Tardiness I: SPT Order Minimizes Total Tardiness When Each Due Date Plus Processing Time Is at Most the Next SPT Completion TimeResearch Paper

A shop that promises delivery dates is judged by how late its orders are, not by how early. For a single machine processing nnn jobs that are all available at time 000, the total tardiness of a processing order,

8 thms3 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

On the Variational Principle II: Under Linearly Independent Active Constraint Gradients, a Bounded-Below Problem Has ε²-Optimal Feasible Points Satisfying the Lagrange Multiplier Rule up to εResearch Paper

The classical Lagrange multiplier rule and its inequality-constrained form, the Karush–Kuhn–Tucker (KKT) conditions, are necessary conditions satisfied at a minimizer of a constrained problem. In finite dimensions, a continuous function bounded below on a closed bounded feasible set attains its minimum, so the rule describes an actual point. In an…

7 thms3 active usersReviewed
🏆Completed
OptimizationProbabilityStochastic Systems·Captain: mikedeng1

Dimensioning Large Call Centers I: The Rationalized Staffing Function Is Asymptotically OptimalResearch Paper

A call center with NNN agents facing Poisson arrivals at rate λ\lambdaλ and exponential service at rate μ\muμ is the M/M/N (Erlang-C) queue. Choosing NNN trades the cost of agents against the cost of customers waiting, and in practice it is done with the square-root safety-staffing rule N≈R+yRN \approx R + y\sqrt RN≈R+yR​, where R=λ/μR = \lambda/\muR=λ/μ is the offered load. Borst,…

22 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory IX: Kingman's Upper Bound on the G/G/1 Queue WaitTextbook

The single-server queue with general independent interarrival and service times, the G/G/1 queue, is the basic model of a congested resource: a machine, a link, a checkout. For Markovian arrivals or services the mean wait has a closed form (the Pollaczek–Khintchine formula for M/G/1, the geometric law for G/M/1). For general distributions it has none, and…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

A Multicut Algorithm for Two-Stage Stochastic Linear Programs 2: Multicut for Simple Recourse Stops Within J·m2 + 1 IterationsResearch Paper

Two-stage stochastic linear programs model decisions taken before uncertainty is resolved (first stage) and corrected afterwards at a cost (second stage, the recourse). The standard solution method for problems with finitely many scenarios is the L-shaped method of Van Slyke and Wets (1969), an outer linearization in the style of Benders decomposition: a…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games IV: For Symmetric Games the Maximum Social Cost Price of Anarchy Is at Most 5/2Research Paper

The price of anarchy measures how much a system of selfish agents loses compared with a centrally optimized one: it is the worst ratio, over all Nash equilibria, between the social cost of the equilibrium and the optimal social cost. Koutsoupias and Papadimitriou introduced it in 1999 (Worst-case equilibria, STACS 1999), and bounding it for routing and…

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

The Price of Anarchy of Finite Congestion Games I: The Pure Price of Anarchy of the Average Social Cost Is 5/2Research Paper

When many independent users share a resource whose cost grows with use (links of a network, servers, machines), each user chooses for itself, and the outcome is a Nash equilibrium rather than a socially optimal allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures the cost of this decentralisation: the worst…

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

A Multicut Algorithm for Two-Stage Stochastic Linear Programs 1: Worst-Case Bound on Multicut Major IterationsResearch Paper

Two-stage stochastic linear programs with recourse are a standard model for planning under uncertainty: a first-stage decision xxx is taken before a random outcome ξ\xiξ is observed, and a second-stage (recourse) decision yyy corrects for it afterwards at a cost. When ξ\xiξ has finitely many realizations, the problem is a large but structured linear program, and…

12 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 4: Restarting a Bounded-Cost Algorithm Is (1+ε)α-Competitive in Games of Finite DiameterResearch Paper

Competitive analysis compares an online algorithm, which must answer each request before seeing the next, with the optimal off-line solution of the same request sequence. Ben-David, Borodin, Karp, Tardos and Wigderson (Algorithmica 11, 1994) set up a general framework, request-answer games, in which paging, the KKK-server problem and metrical task systems are…

10 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 3: An Augmented Potential Function Yields an Explicit Deterministic α∘β-Competitive AlgorithmResearch Paper

Competitive analysis measures an online algorithm, which must answer each request before seeing the next, against the best off-line answer to the whole request sequence. Randomized online algorithms are often much better than deterministic ones against an oblivious adversary, who fixes the requests in advance; the paging problem is the standard example.…

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationStochastic Systems·Captain: mikedeng1

Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance II: An O(n²) Extended Formulation of the Multiclass M/M/1 Performance PolymatroidResearch Paper

A single server shared by several classes of customers is the basic model of scheduling under uncertainty: jobs of different types arrive at random, need random amounts of work, and a scheduler decides at every moment which type to serve. A classical way to optimize such a system, the achievable region approach, describes the set of all performance vectors…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: mikedeng1

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 3: Fractional Double Greedy on the Multilinear Extension Achieves 1/2 of the OptimumResearch Paper

Unconstrained submodular maximization (USM) asks for a subset SSS of a finite ground set N\mathcal NN maximizing a nonnegative submodular function fff. It contains Max-Cut, Max-DiCut and maximum facility location as special cases, and it is the basic subproblem of many constrained submodular maximization algorithms. Because fff is given only through a value oracle,…

11 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 1: α-Competitiveness Against Adaptive On-Line and β Against Oblivious Adversaries Give a Deterministic α∘β-Competitive AlgorithmResearch Paper

An online algorithm must answer each request before it sees the next one. Its performance is compared with an optimum that may choose all its answers after seeing the complete request string. Randomization can improve an online algorithm's guarantee when the request string is fixed in advance. The comparison changes when an adversary chooses later requests…

11 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Power of Randomization in On-Line Algorithms 2: The Bound α∘β Against Adaptive Off-Line Adversaries Is TightResearch Paper

An on-line algorithm must answer each request as it arrives, without knowing the requests to come; paging, caching, the kkk-server problem and metrical task systems are standard examples. Its quality is measured by competitive analysis: its cost is compared with the cost of an optimal off-line solution that knows the whole request sequence. For randomized…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry·Captain: mikedeng1

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed: The Lattice-Point Count of an Integral Simplex Is a Short Signed Sum over Primitive ConesResearch Paper

How many integral points does a polytope contain? The question arises in integer programming, where it measures the size of a feasible set, in combinatorics, where many enumeration problems are lattice-point counts in a polytope (contingency tables, magic squares, flows), in the representation theory of Lie groups, and in the analysis of loop nests in…

16 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Secretary Problems: Weights and Discounts 3: An O(log n)-Competitive Algorithm for the Discounted Secretary ProblemResearch Paper

In the secretary problem, nnn candidates with arbitrary values arrive one at a time in a uniformly random order, and an online decision maker must accept or reject each candidate on arrival, irrevocably, keeping at most one. The rule that observes the first n/en/en/e candidates and then accepts the first one better than everything seen so far selects the best…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: mikedeng1

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 1: Pseudo-Dimension Bound from a Piecewise-Decomposable Dual ClassResearch Paper

Many algorithms in operations research and computer science have tunable parameters: sequence-alignment weights, clustering linkage interpolations, branch-and-bound branching rules, auction reserve prices. In data-driven algorithm design the parameters are chosen by optimizing average performance over a training set of problem instances drawn from an…

14 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Sequencing with Earliness and Tardiness Penalties: With Due-Date Tolerances, the Least Optimal Common Due Date Puts One Job at an End of Its Tolerance WindowResearch Paper

Earliness/tardiness (E/T) scheduling penalizes a job both for finishing late and for finishing early. It models just-in-time production, where an early job ties up inventory and a late one delays a customer. Baker and Scudder's review (Oper. Res. 38 (1990) 22–36) organized the single-machine E/T literature around a short list of structural properties of…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

A Polylogarithmic-Competitive Algorithm for the k-Server Problem: Randomized k-Server Is O(log² k · log³ n · log log n)-Competitive on Every n-Point MetricResearch Paper

The k-server problem (Manasse, McGeoch and Sleator, 1990) is the central problem of online computation: kkk servers sit on points of a metric space, requests arrive one at a time at points of the space, and each request must be served by moving a server to it, at a cost equal to the distance travelled. An online algorithm decides without knowing future…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: mikedeng1

Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time: Delayed SWPT Has Competitive Ratio 2Research Paper

A single machine must process nnn jobs that arrive over time. Job jjj is released at time rjr_jrj​, needs pjp_jpj​ units of uninterrupted processing, and has weight wj>0w_j > 0wj​>0; the goal is to minimize the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​. Offline, with all release dates equal to zero, Smith's rule (sequence by nondecreasing pj/wjp_j/w_jpj​/wj​) is optimal (Smith 1956);…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Correlated Equilibrium as an Expression of Bayesian Rationality I: Bayes Rationality at Every State Yields Exactly the Correlated Equilibrium DistributionsResearch Paper

Nash equilibrium is the standard solution concept for strategic games, but it is usually justified by appeal to what players "would" do once they somehow coordinate on a profile. Correlated equilibrium, introduced by Aumann (J. Math. Econ. 1, 1974), enlarges the set of outcomes by letting players condition their actions on correlated private signals. In Corr…

9 thms3 active usersReviewed
🏆Completed
ProbabilityStatisticsStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory VIII: Lindley's Integral Equation for the G/G/1 QueueTextbook

The single-server queue with general interarrival times and general service times, written G/G/1 in Kendall's notation, is the model left when every distributional assumption is removed from the classical single-server queue. Customers arrive one at a time, wait in line in first-come, first-served order, and are served one at a time. Almost nothing about it…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Numerical Techniques for Stochastic Optimization IV: Nonstationary Optimization and a Convergence Criterion for Nonmonotone SequencesTextbook

Many stochastic and nondifferentiable optimization problems are not solved by minimizing their true objective f0f^0f0 directly: f0f^0f0 may be nonsmooth, an expectation that cannot be evaluated, or only approximately known. A standard remedy replaces f0f^0f0 by a sequence of "good" approximations F0(⋅,s)F^0(\cdot, s)F0(⋅,s) (smoothed versions, sample averages, perturbations) that…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources II: A Time-Feasible Strict Order Is Feasible iff It Breaks Up Every Minimal Forbidden SetTextbook

Resource-constrained project scheduling asks for start times of the activities of a project so that prescribed time lags between activities are respected and, at every moment, the activities in progress do not require more of any renewable resource (staff, machines, reactors) than is available. When the time lags include maximum time lags (deadlines…

9 thms3 active usersReviewed
PreviousPage 59 of 106Next

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