Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Linear Optimization

468 missions · 368 completed

Missions

Open100Completed368All468
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: iris

Approximate Submodularity in Network Design Problems: Every Greedy-Type Heuristic of Algorithm 1 Is a (1 − (1 − 2/K)^K)/2 ≥ (1 − e^{−2})/2 Approximation for Flexibility DesignResearch Paper

Process flexibility lets a plant, warehouse or server pool serve more than one product or customer class. A firm that cannot predict which products will be in demand chooses, before demand and capacity are realized, which supply–demand pairs to connect; after the uncertainty resolves it routes capacity to demand along the installed links. Since Jordan and…

24 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Assign-to-Seat: Dynamic Capacity Control for Selling High-Speed Train Tickets: re-solving a dynamic primal loses O(√θ) revenue against the hindsight optimum, and O(1) under no early endingResearch Paper

Railway operators in China sell tickets for high-speed trains on routes with many intermediate stops, at fares fixed by regulation. A ticket from stop iii to stop j+1j+1j+1 uses legs i,…,ji,\dots,ji,…,j, and at the moment of purchase the passenger must be given one seat for the whole trip. Seats cannot be swapped later. This assign-to-seat restriction is absent from…

19 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds: the sampled dual LP optimum converges to the stochastic-program optimum with E‖p_n − p‖² ≤ C·m log m·log log n / nResearch Paper

Online linear programming (OLP) models sequential resource allocation: orders (rj,aj)(r_j,a_j)(rj​,aj​) arrive one at a time, each must be accepted or rejected on arrival, and accepted orders consume the capacities bbb of a linear program. It covers network revenue management, online auctions, matching and the multi-secretary problem. Almost every OLP algorithm uses the same…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsDiscrete Geometry·Captain: iris

Combinatorial Optimization (Cook et al.) VIII: Edmonds' Matching Polytope Theorem for Loopless Graphs (corrected: loopless)Textbook

A matching in a graph is a set of edges no two of which share an end. Finding a matching of maximum total weight is one of the basic problems of combinatorial optimization: it models pairing tasks (assigning workers, pairing pen movements of a plotter, the postman and T-join problems of the same book) and it sits inside many algorithms as a subroutine. The…

34 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) III: Hoffman's Circulation Theorem with Infinite Bounds and Its Integral FormTextbook

Many combinatorial problems reduce to one question: can a prescribed amount of material be routed through a network without breaking any arc limit? Transportation problems, assignment and scheduling constraints, and the feasibility phase of minimum-cost flow all take this form. Hoffman's circulation theorem (Hoffman, 1960) answers it with a certificate: if…

23 thms4 active usersReviewed
Complexity TheoryDynamical SystemsOptimization·Captain: iris

Robust-to-Dynamics Optimization: With ρ(G) < 1, P Bounded and 0 ∈ int P, S = S_r for a Polynomial-Time-Computable r, and R-LD-LPs with ρ(G) ≤ ρ* < 1 Are Solvable in Polynomial TimeResearch Paper

A linear program assumes that a decision, once taken, stays where it was put. In many applications the decision is an initial state that then evolves under known dynamics: a portfolio drifting under a linear model of returns, an inventory or production profile propagated by a transition matrix, the state of a controlled system after its input is fixed.…

40 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: iris

Zero-Sum Games and Linear Programming Duality: Every Max-Min Strategy of Dantzig's Game with One Extra Row Yields Optimal LP Solutions or Certifies That No Optimal Solution ExistsResearch Paper

Linear programming duality and the minimax theorem for zero-sum games are two faces of the same convexity fact. The classical direction, from LP duality to the minimax theorem, is textbook material: the optimal strategies of a matrix game are the optimal solutions of a pair of dual LPs. The converse direction, solving an LP by solving a game, goes back to Da…

23 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Robust Assortment Optimization Under the Markov Chain Choice Model: Min-max duality and optimal robust assortmentsResearch Paper

A retailer chooses which products to offer before learning exactly how customers will substitute between them. A product that looks attractive under estimated demand can perform poorly when those estimates are wrong. Robust assortment optimization evaluates each offer set by its worst expected revenue over a specified set of possible customer models. The…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Minimum Label s-t Cut has Large Integrality Gaps: Nearly cube-root integrality gap for the strengthened relaxationResearch Paper

A network failure can remove several connections at once. When the connections share a physical resource, paying for or disabling that resource acts on an entire class of edges. The minimum label s-t cut problem captures this distinction: edges carry labels, and the cost of removing a label is paid once, regardless of how many edges have that label. Zhang…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Production Planning by Mixed Integer Programming IV: An Extended Formulation for the Mixing SetTextbook

Mixed-integer production models combine quantities that vary continuously with decisions counted in whole units. A relaxation that allows the latter quantities to be fractional can admit points excluded by every implementable plan. The convex hull of the original feasible set describes the strongest convex relaxation in the same variables. Understanding…

9 thms4 active usersReviewed
CombinatoricsEconomics·Captain: mikedeng1

Every Choice Function Is Pro-Con Rationalizable: Disjoint Sets of Pro- and Con-Orderings Under Which Each Choice Set's Chosen Alternative Is the One with More Pros Than ConsResearch Paper

Revealed-preference theory asks which observed choices can be explained by a decision procedure. The classical answer, maximization of a single preference, explains only choice functions that satisfy consistency conditions such as the weak axiom, and observed choices, including the menu effects in Luce and Raiffa's dinner example, often violate them. A…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms IV: Interior Iterates Identify the Strict Complementarity PartitionTextbook

Interior-point methods for linear programming generate a sequence of strictly positive primal-dual points that converges to the optimal set but never reaches it. The simplex method, by contrast, stops at an exact optimal vertex. Practical solvers and sensitivity analysis both need an exact answer: which variables are positive at optimality, and what the…

10 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms I: The Central Path Converges to the Analytic Centers of the Optimal FacesTextbook

Primal–dual interior-point methods are the standard polynomial-time algorithms for linear programming. They do not walk along the vertices of the feasible polyhedron as the simplex method does. They follow a smooth curve through its interior, the central path, toward the optimal set. Every complexity bound for these methods is a statement about iterates…

7 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsDynamic ProgrammingOperations Research+2·Captain: Shuze Chen

Multi-armed Bandit Allocation Indices IX: Suboptimality Bounds for Branching Bandits and Index Policies on Parallel MachinesTextbook

Gittins index policies are optimal for a single server choosing among alternative bandit processes, and the achievable region method of Bertsimas and Niño-Mora (Math. Oper. Res. 1996) explains why: when the performance vectors of a scheduling system satisfy generalized conservation laws, the region they fill is a polytope whose optimal vertex is an index…

11 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Consensus Halving for Sets of Items: For n Agents with Additive Utilities a Consensus Halving That Cuts at Most min{n, m} of the m Items Always ExistsResearch Paper

Consensus halving asks for a division of a resource into two parts that every one of nnn agents values equally, so that a group with heterogeneous preferences can agree that the two parts are of the same worth. The classical setting is a divisible interval (a cake or a necklace), where Simmons and Su (2003), building on Hobby and Rice (1965), showed that nnn cut…

24 thms4 active users
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Robust Optimization Approach to Process Flexibility Designs with Contribution Margin Differentials: The Alternate Long Chain Is Worst-Case Optimal Among Balanced Two-Margin Long ChainsResearch Paper

A factory can respond to uncertain demand by allowing a plant to make more than one product. Those extra capabilities cost money, so the design question is where to place a limited number of plant–product links. The usual measure of a flexible production system is the number of units sold. When products have different contribution margins, however, two…

23 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand II: A Route Whose Reduced Cost Exceeds ub − φ(RF1) Is in No Optimal Solution of the Routing Subproblem SF1Research Paper

Grocery chains and restaurants that promise delivery within an hour or less must decide, at each dispatch epoch, which drivers to send out and along which routes. Liu and Luo (arXiv:2107.13058v3; Manufacturing & Service Operations Management, 2023) model this as a finite-horizon dynamic program and solve its per-period approximation with a logic-based…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios II: In the Deterministic Case Multi-price Ranking Is minᵢ F(𝒫ᵢ)-CompetitiveResearch Paper

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets I: Under Moment Bounds, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

In many planning problems the decision changes the uncertainty it faces. Opening a facility raises the demand observed near it; a maintenance decision changes the failure distribution of a component; a price shifts the demand law. Decision-dependent uncertainty of this kind breaks the standard assumption of stochastic programming that the probability…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets II: Under Mean and Covariance, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

Many planning problems are solved in stages. A decision is taken, uncertainty is revealed, and the next decision reacts to it. Facility location, capacity expansion and network design all fit this pattern. In a growing class of such problems, the distribution of the uncertainty depends on the decision: opening a facility changes the demand it attracts, and…

6 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 2: The K-Adaptability Problem with Objective Uncertainty Is Equivalent to the MILP (5)Research Paper

Many planning problems are decided in two stages. A here-and-now decision xxx is taken before an uncertain parameter vector ξ\xiξ is observed, and a wait-and-see decision yyy is taken afterwards. When the wait-and-see decision is binary (which route to drive, which facility to open, which machine to schedule), the resulting two-stage robust binary program has no…

11 thms4 active usersReviewed
Machine LearningStatistics·Captain: mikedeng1

Fast Rates for Contextual Linear Optimization 2: Any Algorithm Choosing from a Policy Class of Natarajan Dimension η Has Regret ≥ (ρ(Z)/2e⁴)((η−1)/n)^((1+α)/(2+α)) on Some Margin-α InstanceResearch Paper

In contextual linear optimization (CLO) a decision maker observes a covariate XXX (features of a day, a customer, a network state) and then chooses a decision zzz from a polytope Z\mathcal ZZ to minimise an uncertain linear cost Y⊤zY^\top zY⊤z. Shortest-path routing with predicted travel times and inventory or portfolio decisions driven by forecasts are standard…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Greed Works – Online Algorithms For Unrelated Machine Stochastic Scheduling 2: Greedy Assignment With Nominal Start Times Is (7.216 + 3.608Δ)h(Δ)-Competitive in the Online-Time ModelResearch Paper

Scheduling jobs on parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport V: A Feasible Pair of Kantorovich Potentials Is Optimal or Strictly Improves Along a Direction (1_S, −1_S′)Textbook

The discrete optimal transport problem between two histograms is a linear program, and much of the algorithmic theory of optimal transport is the theory of solving that linear program well. Chapter 3 of Peyré and Cuturi's Computational Optimal Transport (Foundations and Trends in Machine Learning, 2019) surveys the classical combinatorial solvers: the…

9 thms4 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 3: BLP Solves PCSP(A, B) iff Pol(A, B) Has Symmetric Functions of All Arities iff Q_conv Maps to Pol(A, B)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a finite structure I\mathbf II over the same signature, promised to map to A\mathbf AA; the task is to find a homomorphism to the weaker structure B\mathbf BB (or, in the decision…

17 thms4 active usersReviewed
PreviousPage 3 of 19Next

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