Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Dynamic Programming and Optimal Control VII: Infinite Horizon ProblemsTextbook

Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: wenxinzhang

Vector Space Methods V: Convex Separation and Distance DualityTextbook

Linear approximation is only one instance of distance minimization. Feasible sets in optimization are typically convex rather than subspaces, so a useful certificate must compare a target point with an entire convex set and must allow an affine offset. Chapter 5 of Luenberger's Optimization by Vector Space Methods builds this certificate through geometric…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: Shuze Chen

Convex Optimization IV: Löwner–John EllipsoidsTextbook

Every full-dimensional convex body is sandwiched between an ellipsoid and its nnn-fold dilation: shrinking the minimum-volume covering (Löwner–John) ellipsoid E\mathcal{E}E about its centre x0x_0x0​ by the factor 1/n1/n1/n lands inside the body,

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization XII: Interior Point Methods and Path FollowingTextbook

Interior point methods solve linear programs by moving through the interior of the feasible set instead of along its edges — the approach that turned Karmarkar's 1984 breakthrough into today's practical large-scale solvers. This mission formalizes the primal path following algorithm of Chapter 9 of Bertsimas–Tsitsiklis. For μ>0\mu > 0μ>0 the logarithmic barrier

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization XI: The Ellipsoid MethodTextbook

Can the feasibility of a system of linear inequalities be decided in a provably small number of iterations? The ellipsoid method — the algorithm with which Khachiyan showed in 1979 that linear programming is polynomially solvable — answers this with pure convex geometry. This mission formalizes Chapter 8 of Bertsimas–Tsitsiklis. An ellipsoid is

14 thms3 active usersReviewed
🏆Completed
Linear Optimization·Captain: Shuze Chen

Introduction to Linear Optimization IX: Network Flow IntegralityTextbook

Why do network linear programs return integer answers for free? This mission formalizes the structural theory of the minimum cost network flow problem of Chapter 7 of Bertsimas & Tsitsiklis: a directed graph G=(N,A)G=(\mathcal{N},\mathcal{A})G=(N,A) with external supplies bib_ibi​, arc costs cijc_{ij}cij​, and the node-arc incidence matrix A\mathbf{A}A — an n×mn\times mn×m matrix in which…

18 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization VIII: Sensitivity Analysis and Subgradients of the Optimal CostTextbook

How does the optimal cost of a linear program respond when the problem data change? Chapter 5 of Bertsimas-Tsitsiklis studies the standard form problem min⁡{c′x∣Ax=b, x≥0}\min\{c'x \mid Ax = b,\ x \ge 0\}min{c′x∣Ax=b, x≥0} (rows of AAA linearly independent) as the requirement vector bbb and the cost vector ccc vary. On the convex set S={b∣P(b)≠∅}S = \{b \mid P(b) \neq \emptyset\}S={b∣P(b)=∅} of feasible right-hand sides,…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization V: Duality TheoryTextbook

Every linear programming problem has a shadow. To the primal min⁡c′x\min c'xminc′x we associate the dual max⁡p′b\max p'bmaxp′b, whose variables price the primal constraints: one dual variable per primal constraint and one dual constraint per primal variable, with signs governed by the correspondence of Table 4.1. This mission formalizes §4.1–4.5 of Bertsimas–Tsitsiklis: the dual of…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization IV: The Simplex MethodTextbook

How does one actually solve a linear program? Chapter 2 showed that if a standard-form problem min⁡c′x\min c'xminc′x subject to Ax=bAx = bAx=b, x≥0x \ge 0x≥0 has an optimal solution, it has an optimal basic feasible solution; the simplex method searches among basic feasible solutions, moving along edges of the feasible set in cost-reducing directions. This mission formalizes the…

16 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization I: Polyhedra and Basic Feasible SolutionsTextbook

Every linear programming problem asks to minimize a linear cost c′xc'xc′x over a polyhedron — a set of the form P={x∈Rn∣Ax≥b}P = \{x \in \mathbb{R}^n \mid Ax \ge b\}P={x∈Rn∣Ax≥b}, or in standard form {x∣Ax=b, x≥0}\{x \mid Ax = b,\ x \ge 0\}{x∣Ax=b, x≥0}. Chapter 2 of Bertsimas–Tsitsiklis develops the geometry of these feasible sets, and its central achievement is making the intuitive notion of a "corner point"…

9 thms3 active usersReviewed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Extending Tardos's Theorem to Separable Convex Quadratic ProgrammingResearch Paper

A strongly polynomial algorithm for a class of optimization problems uses a number of arithmetic operations bounded by a polynomial in the dimensions alone, independently of how large the numbers in the input are. Whether linear programming admits such an algorithm is open (Smale's 9th problem). Tardos (1986) proved the most useful partial answer: for an…

25 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Packing Bins in the Euclidean Plane: An Almost-Optimal Approximation for Unsplittable Capacitated Vehicle RoutingResearch Paper

The Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, asks for a cheapest set of delivery routes from a depot when each vehicle can carry at most QQQ units. It is a central model of logistics, and most standard benchmark sets use Euclidean distances. In the unsplittable version every client's demand must be delivered by a…

22 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Beyond Gomory-Hu: All-Pairs ×\times× All-Pairs Mincuts in O(n)O(n)O(n) SpaceResearch Paper

Two classical representations of minimum cuts in an undirected weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) with nnn vertices answer complementary questions. The Gomory–Hu tree (Gomory–Hu 1961) stores, in O(n)O(n)O(n) space, one minimum (x,y)(x,y)(x,y)-cut for every terminal pair x,yx,yx,y, but only one of the possibly many. The Picard–Queyranne representation (Picard–Queyranne, Math. Programming Study…

41 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Minimum-Cost kkk-Arborescence Packing in O~(km+k4n)\tilde O(km+k^4 n)O~(km+k4n) TimeResearch Paper

A packing of kkk arc-disjoint spanning arborescences rooted at a common vertex rrr keeps every vertex reachable from rrr after the deletion of any k−1k-1k−1 arcs. Finding such a packing of minimum total cost is a building block of approximation algorithms for network design, including minimum-cost kkk-edge-connected spanning subgraphs and flexible graph connectivity, and…

37 thms2 active usersReviewed
Graph TheoryOperations Research·Captain: mikedeng1

Harmonic Ranking for Edge-Weighted Oblivious MatchingResearch Paper

A query–commit matching problem combines discovery with allocation. A successful query can force an immediate decision, so learning which pairs are available cannot be separated from choosing a matching. This matters in the mathematical study of allocation rules that must act without seeing the complete compatibility graph. The edge-weighted oblivious model…

30 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Better Approximation for Sparsest Cut Oracles with Balance GuaranteesResearch Paper

A sparse cut separates a network across edges whose total capacity is small compared with the weight on either side. Such cuts identify bottlenecks. They are also used repeatedly when dividing graphs into expanding pieces and constructing representations of network congestion. In these applications, the size of a returned piece matters: repeatedly removing…

32 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Bootstrap, Recolor, Verify: Hierarchical Integrality Gap Instance for 0-extensionResearch Paper

Assigning network vertices to prescribed terminals is a basic form of discrete labeling. A label has a location in a metric space, and an edge pays its weight times the distance between its endpoints' labels. The optimization problem asks for a labeling of minimum total cost while keeping the terminals fixed. Researchers studying approximation algorithms…

17 thms2 active usersReviewed
Computational Complexity·Captain: mikedeng1

Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Quantum SeparabilityResearch Paper

A real tensor is an array with several indices. Its size grows exponentially with its number of indices, but algorithms are measured against that explicit array size. A basic geometric question asks whether the array belongs to the unit ball of the nuclear norm, which measures the cost of expressing it as a sum of product arrays. Bernasconi and Malavolta…

31 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev InequalitiesResearch Paper

Sampling from a probability density πV(dx)∝e−V(x) dx\pi_V(dx)\propto e^{-V(x)}\,dxπV​(dx)∝e−V(x)dx on Rd\mathbb R^dRd, given only evaluations of VVV and its gradient, is a basic task in Bayesian computation, statistical physics and randomized optimization. Algorithms such as the unadjusted and Metropolis-adjusted Langevin methods and Hamiltonian Monte Carlo are analysed in exactly this model,…

21 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted GraphsResearch Paper

The Minimum kkk-Cut problem asks, for an undirected graph with positive edge capacities, for a set of edges of least total capacity whose removal leaves at least kkk connected components. For k=2k=2k=2 it is the global minimum cut, solvable in near-linear time (Karger 2000; Henzinger, Li, Rao, Wang 2024). For fixed kkk the problem is polynomial but the exponent grows…

27 thms2 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

Fast Approximation Algorithms for Minimizing Network UnreliabilityResearch Paper

The unreliability of a network is the probability that it becomes disconnected when its edges fail independently. Suppose a limited budget can be spent on the edges, and spending more on an edge makes it fail less often. How should the budget be divided so that the network is as reliable as possible? Chakrabarty, Mehta and Vazirani raised this question and…

19 thms2 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Improved Steiner Forest Approximation via Cut SpacesResearch Paper

Steiner Forest is the basic problem of buying connections in a network. A network has nonnegative edge costs, and a list of vertex pairs must each be joined by a path; an edge is paid for once, however many paths use it. Shortest paths and Steiner trees are special cases. The problem is NP-hard, so the question is the best approximation factor: a bound rrr suc…

16 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

The Complexity of Private Signaling in Nonatomic Routing GamesResearch Paper

A traffic principal can know more about road conditions than individual drivers. Sending every driver the same report is one option; sending different private route recommendations is another. The computational question is whether a principal can find private recommendations with low expected total latency while keeping each recommendation approximately…

19 thms2 active usersReviewed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: Shuze Chen

Approaching Optimality for Dense Bipartite MatchingsResearch Paper

The maximum bipartite matching problem asks, for a bipartite graph GGG with sides LLL and RRR, for the largest number ν(G)\nu(G)ν(G) of edges no two of which share a vertex. It is the most basic case of maximum flow and of linear programming over an integral polytope, and its running time on dense graphs has long been a test of algorithmic technique. Combinatorial…

17 thms2 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: Shuze Chen

RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing GamesResearch Paper

Sellers of digital and physical goods set prices in competition for the same pool of buyer money. When buyers have hard budgets rather than quasilinear utilities, the sellers' revenues are coupled through those budgets: a price change by one seller moves money to or from every other seller. The textbook equilibrium notion for such a pricing game is the Nash…

14 thms2 active usersReviewed
PreviousPage 56 of 93Next

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