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

Robust Solutions of Uncertain Linear Programs I: Under Constraint-wise Uncertainty and the Boundedness Assumption the Robust Counterpart Is No Worse Than the Worst InstanceResearch Paper

A linear program is solved with data that, in practice, is rarely known exactly: coefficients come from measurements, estimates or forecasts. Robust optimization asks for a solution that remains feasible for every realization of the data in a prescribed uncertainty set, and among those the one with the best guaranteed objective value. Ben-Tal and Nemirovski…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Solving Linear Programs in the Current Matrix Multiplication Time: The Stochastic Central Path Falls Back to a Classical Step with Probability at Most 10/n² per IterationResearch Paper

Linear programming, min⁡{c⊤x:Ax=b, x≥0}\min\{c^\top x : Ax=b,\ x\ge0\}min{c⊤x:Ax=b, x≥0} with A∈Rd×nA\in\mathbb R^{d\times n}A∈Rd×n, is the basic model of operations research, and the complexity of solving it is a central question of algorithm theory. Interior-point methods follow the central path: primal–dual pairs (x,s)(x,s)(x,s) with x,s>0x,s>0x,s>0 and xisi=tx_is_i=txi​si​=t for every iii, as the path parameter ttt decreases to 000. A…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationStatistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 4: Existence of the Maximum Likelihood Estimate Is Decided by a Quadratic ProgramResearch Paper

The conditional logit model assigns probabilities to choices among alternatives whose observable attributes differ from trial to trial. A fitted parameter vector is usually obtained by maximizing a log-likelihood. For a finite data set, however, maximization need not produce a finite vector: some directions in parameter space can keep improving the…

5 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time 2: The Two-Phase Shadow-Vertex Simplex Method Has Polynomial Smoothed ComplexityResearch Paper

The simplex method solves linear programs by moving between vertices of a feasible polyhedron. Its worst-case number of moves can grow exponentially, yet it often performs well on ordinary inputs. Worst-case examples alone therefore give an incomplete account of the method’s behavior. Spielman and Teng introduced smoothed analysis to measure expected…

22 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources III: Active, Semiactive, Pseudoactive and Quasiactive Schedules Are Minimal Points of the Feasible RegionTextbook

Exact and heuristic methods for resource-constrained project scheduling do not search the whole continuum of start-time vectors. They enumerate a finite candidate set that is guaranteed to contain an optimal schedule. For machine scheduling and precedence-only project scheduling the classical candidate sets (semiactive and active schedules) are defined by…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VI: Stable, Semistable, Pseudostable and Quasistable Schedules Are Extreme Points of the Feasible RegionTextbook

Resource-constrained project scheduling with minimum and maximum time lags is the model behind make-to-order production, process-industry batch planning and large engineering projects. When the objective is the project duration or another regular function (nondecreasing in every start time), an optimum can be found among schedules that cannot be shifted to…

12 thms2 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming XI: The KKT Conditions and the Unique Smallest Enclosing BallTextbook

The smallest enclosing ball problem asks, for finitely many points p1,…,pn∈Rdp_1,\dots,p_n\in\mathbb{R}^dp1​,…,pn​∈Rd, for a ball of the smallest radius that contains all of them. It appears in clustering, in collision detection and bounding-volume hierarchies, in facility location (placing one service point so that the farthest client is as close as possible), and in the…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Understanding and Using Linear Programming III: The Simplex Method with Bland's Rule Never CyclesTextbook

The simplex method, introduced by G. B. Dantzig in 1947, is the standard algorithm for linear programming and remains the core of commercial solvers. It moves from one basic feasible solution to another by pivot steps, and at each step a pivot rule chooses which variable enters and which leaves the basis. For several natural rules, including Dantzig's…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming X: Pairwise Intersecting d-Intervals Have a Transversal of Size 2d²Textbook

A basic question of combinatorial geometry asks when a family of sets can be pierced (or stabbed) by few points. For intervals on the real line the answer is classical: if every two of finitely many closed intervals intersect, one point meets all of them, namely the rightmost left endpoint. This is the one-dimensional case of Helly's theorem. The situation…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationRandom Matrix Theory·Captain: mikedeng1

Understanding and Using Linear Programming IX: Basis Pursuit Recovers Sparse Solutions Exactly iff the Kernel Misses the CrosspolytopeTextbook

A deep-space probe sends a vector w∈Rkw\in\mathbb{R}^kw∈Rk encoded as z=Qw∈Rnz=Qw\in\mathbb{R}^nz=Qw∈Rn, and up to about 8% of the transmitted numbers may be corrupted arbitrarily. Section 8.5 of Matoušek and Gärtner's Understanding and Using Linear Programming (Springer 2007, DOI 10.1007/978-3-540-30717-4) shows that decoding reduces to finding a sparse solution of an…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming VIII: The Delsarte Linear Programming Bound for Binary CodesTextbook

A binary error-correcting code is a set of nnn-bit words chosen so that the words stay distinguishable after a few bits have been corrupted in transmission. A code can correct any rrr errors exactly when every two of its words differ in at least 2r+12r+12r+1 positions. The more words the code has, the more information each transmitted block carries. So the central…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Randomized Linear Programming Method for Computing Network Bid Prices II: Directional Derivatives of Expected Perfect-Information Revenue Are Expected LP ValuesResearch Paper

Airlines, hotels and railways sell a fixed stock of capacity on several resources at once: a passenger flying from Boston to Los Angeles through Chicago uses a seat on two flight legs. Network revenue management decides which requests to accept, and the standard control is a bid price per leg: accept an itinerary if its fare exceeds the sum of the bid…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Randomized Linear Programming Method for Computing Network Bid Prices I: Averaged LP Dual Prices Are an Unbiased Estimate of the Gradient of Expected Perfect-Information RevenueResearch Paper

Airlines, hotels and railways sell fixed capacity on networks of resources. In network revenue management a request for an itinerary that uses several flight legs is accepted or rejected in real time, and the dominant industrial control is the bid-price control: every leg carries a price, and a request is accepted only if its fare is at least the sum of the…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Understanding and Using Linear Programming VII: LP Rounding Schedules Unrelated Machines Within Twice the Optimal MakespanTextbook

Scheduling indivisible jobs on parallel machines to finish all of them as early as possible is a basic problem in operations research and in the theory of algorithms. In the unrelated machines model each job may take a different time on each machine, with no relation between the rows of the time table, as when machines of different types (black-and-white,…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Understanding and Using Linear Programming VI: The Minimax Theorem for Zero-Sum GamesTextbook

A two-player zero-sum game models any situation in which one party's gain is exactly the other party's loss: a military allocation in the spirit of Colonel Blotto, a sealed-bid contest, rock–paper–scissors. The central question is what each player should do when the opponent is also reasoning about them. John von Neumann answered it in 1928 with the minimax…

14 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Understanding and Using Linear Programming II: Optimal Basic Feasible Solutions and Vertices in Equational FormTextbook

Every finite algorithm for linear programming rests on one structural fact: if a linear program has an optimum at all, it has one at a point singled out by finitely many linear conditions. The simplex method walks between such points, and exact complexity analyses, sensitivity analysis and integrality arguments all start from them. Chapter 4 of J. Matoušek…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Choice-Based Linear Programming Model for Network Revenue Management II: Only Efficient Offer Sets Carry Time in an Optimal CDLP SolutionResearch Paper

Airlines, hotels and rail operators sell many products (an itinerary combined with a fare class) that share a network of finite resources (flight legs, room-nights). When customers choose among whatever products are on offer, the firm's control is no longer "accept or reject a request for product jjj" but which set of products to offer at each moment. The…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming: Foundations and Extensions V: Convergence Rates of the Path-Following MethodTextbook

Interior-point methods are, together with the simplex method, the standard algorithms for linear programming, and the primal–dual path-following method is the form in which they are implemented in most solvers. Unlike the simplex method, it is a one-phase method: it can start from any point whose primal and dual variables are strictly positive, feasible or…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions III: Network Flows, the Integrality Theorem and König's TheoremTextbook

Minimum-cost network flow problems are the largest special class of linear programs met in practice: transportation, distribution, assignment, communication and electric networks, facility location and financial planning all reduce to moving material along the arcs of a directed network from supply nodes to demand nodes at least cost. Chapter 14 of R. J.…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Odd Minimum Cut-Sets and b-Matchings 2: A Capacitated b-Matching Blossom Inequality Is Violated iff G(x, d) Has an Odd Cut of Capacity Less Than OneResearch Paper

A b-matching with upper bounds in a graph G=(V,E)G=(V,E)G=(V,E) assigns a nonnegative integer xe≤dex_e\le d_exe​≤de​ to every edge so that the edges at each node iii carry at most bib_ibi​ in total. Maximizing a linear objective over such assignments is an integer program that contains ordinary matching (b≡1b\equiv 1b≡1, d≡1d\equiv 1d≡1) and appears in assignment, transportation and scheduling models…

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

Selected Topics in Column Generation II: A Strictly Redundant Column Is Never Optimal for the Ratio Pricing ProblemResearch Paper

Column generation solves linear programs with far more columns than can be written down: a restricted master problem holds a few columns, its dual multipliers are passed to a pricing problem, and the pricing problem returns a column to add. It is the standard engine behind branch-and-price for vehicle routing, crew scheduling and cutting stock, where the…

3 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem I: ALGORITHM 1, Linear Grouping with LP Rounding, Is an Asymptotic Approximation SchemeResearch Paper

One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in (0,1)(0,1)(0,1). It is the model behind cutting stock (cutting rolls of paper or steel to ordered widths), memory and file allocation, and batch scheduling on identical machines, and it is NP-hard. Its algorithmic study is therefore about approximation:…

16 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Revenue Management Under the Markov Chain Choice Model IV: Dimension Reduction Recovers a Choice-Based Solution with at Most n+1 Nested Offer SetsResearch Paper

In network revenue management a firm sells nnn products that consume mmm capacitated resources over TTT periods, and in each period it chooses which offer set of products to make available. When customers choose among the offered products according to a choice model, the standard planning tool is the choice-based linear program, which assigns a frequency uS≥0u_S\ge 0uS​≥0…

14 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Single Machine Scheduling with Release Dates I: The Preemptive Time-Indexed and Mean Busy Time LP Relaxations Have the Same Optimal ValueResearch Paper

Minimizing the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​ of jobs with release dates on a single machine, written 1 ∣ rj ∣ ∑wjCj1\,|\,r_j\,|\,\sum w_j C_j1∣rj​∣∑wj​Cj​ in scheduling notation, is strongly NP-hard. Most constant-factor approximation algorithms for it, and for many related scheduling problems, follow one pattern: solve a linear programming relaxation, which gives a…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Revenue Management Under the Markov Chain Choice Model III: The Reduced Linear Program Is Equivalent to the Choice-Based Linear ProgramResearch Paper

Network revenue management decides which products to make available to arriving customers when products share scarce resources: an airline sells itineraries (products) that consume seats on flight legs (resources), and each itinerary has a fare. When customers choose among the offered products, rather than asking for one fixed product, the standard planning…

12 thms2 active usersReviewed
PreviousPage 17 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