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
Operations ResearchOptimization·Captain: mikedeng1

An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities: On Infeasible Systems, OEA Returns a Solution of (Alt) Within 2m(m+1) ln((m+1)‖u−ℓ‖/(2mτ)) IterationsResearch Paper

A system of linear inequalities may have either a feasible point or a short witness that no feasible point exists. An algorithm that returns the witness is useful when a solver must explain an infeasibility decision rather than merely announce one. The standard ellipsoid method can test feasibility under suitable geometric bounds, but its ordinary output…

11 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Regular Matroids Have Polynomial Extension Complexity: The Independence Polytope of Every Regular Matroid on n Elements Has Extension Complexity O(n⁶)Research Paper

Many combinatorial optimization problems are linear programs over a polytope with exponentially many facets, and one way to solve them by a polynomial-size linear program is to write the polytope as the projection of a higher-dimensional polytope with few facets. The minimum number of facets needed is the extension complexity of the polytope. It is now…

20 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: Shuze Chen

The Traveling-Salesman Problem and Minimum Spanning Trees: The 1-Tree Gap Vanishes Exactly When the Subtour LP Has an Integral Optimal SolutionResearch Paper

The symmetric traveling-salesman problem asks for a cheapest cycle through all nnn vertices of a complete graph with real edge weights. Every exact method for it rests on lower bounds, and the most widely used one comes from Held and Karp's two papers of 1970–71 (Held & Karp 1970; Part II, 1971). Their bound is built from 1-trees, a slight variant of spanning…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Fast and Simple Solutions of Blotto Games: The Nash-Equilibrium Strategies of Colonel Blotto Have a Linear Formulation with O(N²K) Constraints and VariablesResearch Paper

The Colonel Blotto game, introduced by Borel in 1921, is a two-player zero-sum game of resource allocation. Two players distribute their troops over several battlefields, and each battlefield is won or scored according to the troops placed there. It models allocation contests in military planning, political campaigns (budgets across swing states),…

12 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchReinforcement Learning·Captain: mikedeng1

Nonstationary Reinforcement Learning: The Blessing of (More) Optimism I: No Policy Earns More Than the Sum of Per-Step Optimal Gains Plus 4(D_max+1)√((B_r+2D_max B_p)T)Research Paper

Reinforcement learning in a changing environment needs a benchmark that remains meaningful when the transition law and rewards vary from round to round. For a stationary Markov decision process (MDP), the optimal long-run average reward is a standard benchmark. In a nonstationary MDP, summing those stationary optima across rounds is convenient, but it need…

11 thms3 active usersReviewed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Linear Programming and Community Detection 6: The LP Relaxation Fails w.h.p. in the Very Dense and Dense SBM Above Explicit ThresholdsResearch Paper

Community detection asks for a hidden partition of the nodes of a graph from its edges. Its simplest probabilistic benchmark is the two-community stochastic block model (SBM), in which the minimum bisection problem is the maximum a posteriori estimator. That problem is NP-hard, so convex relaxations are used in its place, and the question is when a…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+2·Captain: mikedeng1

Linear Programming and Community Detection 5: The LP Relaxation Recovers the Planted Bisection w.h.p. in the Very Dense SBM When p − q > 1/2Research Paper

The stochastic block model (SBM), introduced by Holland, Laskey and Leinhardt (1983), is the standard random model for networks with community structure, and the basic benchmark for community-detection algorithms (Abbe 2018). In its two-community form the nodes are split into two equal halves, edges inside a half appear with probability ppp, and edges across…

12 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Linear Programming and Community Detection 3: The Metric LP Relaxation Recovers the Planted Bisection When d_in − d_out ≥ n/4 Under Regular SandwichingResearch Paper

The minimum bisection problem asks, for a graph G=(V,E)G=(V,E)G=(V,E) on an even number nnn of vertices, for a split of VVV into two halves of size n/2n/2n/2 that cuts as few edges as possible. It is NP-hard, and it is also the maximum a posteriori estimator for the two-community stochastic block model, the standard random model of networks with community structure. A tractable…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryGraph TheoryMechanism Design+2·Captain: mikedeng1

Designing Approximately Optimal Search on Matching Platforms 1: Some Stationary Equilibrium of Directed Search Attains a Quarter of the First-Best WelfareResearch Paper

Two-sided platforms for dating, freelancing and housing do more than list participants: they decide whom each participant is shown. When search is costly and agents leave the market over time, the platform's choice of assortments (which types of agents meet which, and how often) determines who matches, and agents respond strategically by deciding which…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 3: In Simultaneous Offering With Values at Least τ, a Truncated-LP Value-Ordered Policy Earns ≥ α^τ_k Times the LP BoundResearch Paper

A firm that fills a fixed number of positions from a pool of applicants faces uncertainty at every stage: applicants differ in value, and an offer may be declined. When offers must go out at once, as in a recruiting season with a common deadline, the firm decides a single offer set and lives with however many candidates accept. Sending too few offers leaves…

13 thms3 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Quantum Algorithms for Zero-Sum Games 1: With Step ε/4, Grigoriadis–Khachiyan Sampling Play Yields ε-Optimal Strategies After ⌈16 ln(nm/δ)/ε²⌉ Iterations with Probability ≥ 1 − δResearch Paper

Two-player zero-sum matrix games are the simplest model of strict competition, and computing their value is equivalent to linear programming. Many algorithms in optimization and learning (boosting, online learning with experts, approximate LP and SDP solvers) are, at their core, procedures that approximately solve such a game. For large games the cost of…

10 thms3 active usersReviewed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

A Strongly Polynomial Algorithm for Linear Exchange Markets II: A Z₊-Matrix Polyhedron P_M Lies Between an M2VPI Polyhedron and Its Scaling by B²Research Paper

In a linear exchange market every agent owns one divisible good and has linear utilities over all goods; an equilibrium is a price vector at which every agent can spend its budget on goods that maximize utility per unit of money, and all goods are sold. Computing such an equilibrium in strongly polynomial time, with a number of arithmetic operations bounded…

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

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 1: A Non-Adaptive, Committed LP-Rounding Policy for ProbeTop-k Earns at Least (1 − e^{−k}k^k/k!) Times the LP BoundResearch Paper

Hiring is a pipeline: a firm with kkk openings and a large pool of applicants cannot interview everyone, so it must decide whom to interview, in what order, and whether to hire on the spot. The ProbeTop-k problem models this. Each applicant has a random value with a known distribution, an interview reveals the value, at most TTT interviews may be conducted, and…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Dynamic Matching: Characterizing and Achieving Constant Regret II: In (SPP)-Acyclic Networks the Static Planning Solution Is Given by Surplus Vectors in {−1, 0, 1}ⁿResearch Paper

Centralized markets such as kidney exchanges, ride-sharing platforms and online labor markets match agents who arrive over time. Kerimov, Ashlagi and Gurvich (SSRN 3824407; Management Science, 2023, doi:10.1287/mnsc.2021.01215) study such a market with nnn agent types and ddd feasible multi-way matches. Their main result is that, when a fluid linear program…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretaries with Advice 5: With Binary-Classifier Advice of Recall p and Specificity p′, the Optimal Success Probability Tends to ((1−p′)/p)^((1−p′)/p′)·e^((p−1)/p′)Research Paper

A secretary problem asks a decision maker to choose one candidate from a sequence, without being able to recall a rejected candidate. Each arrival reveals how the candidate compares with those seen earlier, but the decision maker does not know the candidate's final rank. A classifier can provide an additional Yes or No signal about whether the current…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Secretaries with Advice 3: A Closed Form for the Backward-Induction Dual Solution of the Secretary-with-Samples LPResearch Paper

In the secretary problem nnn candidates arrive one at a time in uniformly random order; at each arrival the decision maker sees only how the current candidate compares with the earlier ones and must accept or reject irrevocably, aiming to accept the best candidate overall. Dütting, Lattanzi, Paes Leme and Vassilvitskii, Secretaries with Advice (arXiv:2011.0672…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretaries with Advice 4: With Advice from a Binary Classifier, a Threshold Policy Is OptimalResearch Paper

The classical secretary problem asks a decision maker to choose the best of nnn candidates arriving in random order. A decision must be made when each candidate arrives, before later candidates are seen. In the classical model the decision maker sees only comparisons with earlier candidates. In hiring and selection, a prediction system may also classify an…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretaries with Advice 2: With k Samples, a Threshold Policy Is Optimal for Selecting the Best of n SecretariesResearch Paper

In the classical secretary problem, nnn candidates with distinct qualities arrive in uniformly random order; after each arrival one sees only how the current candidate compares with those already seen, and must irrevocably accept or reject. The goal is to accept the best candidate. Dynkin's rule (skip roughly n/en/en/e candidates, then accept the first one better…

16 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex Optimization·Captain: mikedeng1

Persuading Risk-Conscious Agents: A Geometric Approach II: In Binary Persuasion with a Convex Non-Adoption Region the Convex Program Reduces to a Linear Program over Ω ∪ K₀₁Research Paper

In Bayesian persuasion a sender who observes the state of the world commits to a signaling scheme, a receiver updates her belief by Bayes' rule and acts, and the sender chooses the scheme that maximizes her own expected payoff (Kamenica and Gentzkow 2011). The classical theory assumes the receiver maximizes expected utility, so her payoff is linear in her…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Reducing Marketplace Interference Bias Via Shadow Prices 2: In Expectation the Shadow-Price Estimator Equals the Derivative of the Finite-Sample Partial-Treatment Value FunctionResearch Paper

Two-sided platforms (ride hailing, delivery, freight, cloud capacity) test product changes with user-split experiments: each arriving demand unit is assigned to treatment with probability ρ\rhoρ and to control otherwise. Treated and control units then compete for the same supply, so the outcome of one group depends on the size of the other. This interference b…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

On Solving Multistage Stochastic Programs with Coherent Risk Measures: The Inner-Approximation Policy's Nested Risk-Adjusted Cost Is at Most the Upper Bound yResearch Paper

Multistage stochastic linear programs model decisions taken over time under uncertainty: reservoir releases in hydro-thermal scheduling, production and inventory plans, capacity expansion. Their standard solution method, stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991), approximates each stage's cost-to-go function from below by cutting…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 2: Clique and Lifted Clique Cuts on Pairwise Incompatible Clusters Are ValidResearch Paper

Strategic open pit mine planning decides which parts of an ore body are excavated, when, and where each block of material is sent. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) model the problem as a mixed-integer program, the precedence-constrained production scheduling problem with clusters (PCPSP-C),…

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

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 1: Under G, g ≥ 0 Every Minimal Optimal Schedule Stays inside the Ultimate Pit LimitResearch Paper

Strategic planning of an open pit mine decides, over a horizon of 20 to 50 years, which parts of an ore body are excavated, when, and where the excavated material is sent. A deposit is discretized into blocks, often millions of them, and the decisions are constrained by wall-slope precedences between blocks, by mining and processing capacities, and by…

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

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 4: Hourglass Production Cuts Are Valid under Full and Partial IntegralityResearch Paper

Strategic open pit mine planning decides which parts of an ore body are excavated, in which period, and to which destination (a processing plant, a stockpile, a waste dump) each block of material is sent. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) model this as a mixed-integer program, the precedence-constrained…

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

Multistage Adaptive Robust Optimization for the Unit Commitment Problem II: Under the W_it-Policy, Robust Generation and Ramping Limits Reduce to the Extreme Total-Load ScenariosResearch Paper

Unit commitment (UC) is the daily scheduling problem of electricity system operators: decide which generators are switched on in each hour of the next day, and how much each produces, so that supply meets the net load at minimum cost while respecting generation limits, ramping limits and transmission limits. With growing shares of wind and solar power, the…

6 thms3 active usersReviewed
PreviousPage 8 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