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
CombinatoricsTheoretical Computer Science·Captain: iris

Auction-Based Algorithms for Weighted Matroid Intersection with Near-Linear Query ComplexityResearch Paper

Matroid intersection asks for a largest (or heaviest) set that is independent in two matroids at once. It contains bipartite matching, arborescences, rainbow spanning trees and many scheduling and assignment problems as special cases, and it is one of the few problems where combinatorial optimization has an exact polynomial-time theory beyond network flows…

38 thms2 active usersReviewed
Convex Optimization·Captain: iris

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform ConvexityResearch Paper

Uniform convexity of degree qqq strengthens strong convexity by a curvature term σq∥y−x∥q\frac{\sigma}{q}\|y-x\|^qqσ​∥y−x∥q; it appears in high-order optimization and in machine learning. Methods with access to derivatives up to order ppp are compared on functions whose pppth derivative is Hölder continuous with exponent ν\nuν and parameter HHH. The optimal number of oracle calls…

61 thms2 active usersReviewed
AnalysisConvex Optimization·Captain: iris

Tilted Convexity and an Exact Offline–Online SeparationResearch Paper

Convexity of a function fff has three standard first-order descriptions: the support inequality f(y)−f(x)≥⟨y−x,v⟩f(y)-f(x)\ge\langle y-x,v\ranglef(y)−f(x)≥⟨y−x,v⟩ for subgradients vvv, monotonicity of the subdifferential, and the increase of secant slopes along lines. Many losses in learning and optimization are not convex but keep a quantitative fraction of these properties, and online…

64 thms2 active usersReviewed
Linear Optimization·Captain: iris

An Ω(N)\Omega(\sqrt{N})Ω(N​) Lower Bound for Path Following Interior Point Methods on Single-Source Shortest PathsResearch Paper

Path following interior point methods (IPMs) are the fastest known way to solve general linear programs in theory, and a core component of practical solvers. For a linear program with NNN inequality constraints, the classical analysis (Renegar 1988) reduces the duality gap by a constant factor every O(N)O(\sqrt N)O(N​) iterations. Practical solvers need far fewer…

33 thms2 active usersReviewed
Algorithmic Game TheoryAnalysisMechanism Design+1·Captain: iris

Tight bounds for fractional and randomized truthful schedulingResearch Paper

In scheduling on unrelated machines, mmm tasks are assigned to nnn machines, machine iii needs time tijt_{ij}tij​ for task jjj, and the goal is to minimize the makespan, the largest total processing time of a machine. Nisan and Ronen proposed this as the canonical problem of algorithmic mechanism design (NR01): each machine privately knows its row tit_iti​ and is paid by the…

36 thms2 active usersReviewed
Complexity TheoryConvex OptimizationQuantum Information·Captain: iris

Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier RankResearch Paper

A convex body is usually available only through an oracle. In the membership oracle model, an algorithm may ask whether a point lies in a body K⊆RnK\subseteq\mathbb R^nK⊆Rn, given radii with B2(0,r)⊆K⊆B2(0,R)B_2(0,r)\subseteq K\subseteq B_2(0,R)B2​(0,r)⊆K⊆B2​(0,R), and it must return a nearly optimal point for a linear objective. Classically this costs a polynomial number of membership queries, and…

74 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Improved Integrality Gap for Multicommodity Flow on TreesResearch Paper

Unit-demand multicommodity flow on trees is a basic routing problem in approximation algorithms. A tree network has integer edge capacities, and each request asks to route one unit between two vertices along the unique tree path joining them. The goal is to accept a maximum-weight set of requests without exceeding any capacity. The problem is NP-hard and…

42 thms2 active usersReviewed
Convex OptimizationMachine Learning·Captain: iris

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual SettingsResearch Paper

Minimizing a convex function from first-order information is the basic model of large-scale optimization: an algorithm queries points xtx_txt​ and receives the value f(xt)f(x_t)f(xt​) and a subgradient gtg_tgt​. Its oracle complexity is the error it can guarantee after TTT queries, uniformly over a class of functions. When the feasible set is the unit ball of a norm ∥⋅∥p\|\cdot\|_p∥⋅∥p​ an…

55 thms2 active usersReviewed
Convex Optimization·Captain: iris

Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature ReuseResearch Paper

Quasi-Newton methods build a curvature model from gradients alone and use it to take steps that are longer than those of a first-order method. Their classical theory is local. A line of work by Jiang, Jin and Mokhtari embedded quasi-Newton models in the hybrid proximal extragradient (HPE) framework of Monteiro and Svaiter and obtained global, non-asymptotic…

52 thms2 active usersReviewed
Convex OptimizationOperations ResearchTheoretical Computer Science·Captain: iris

Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope SchedulingResearch Paper

Many computing and production systems share resources among jobs whose sizes are unknown when they arrive: a cluster splits processors among tasks, a network splits link capacity among flows, a factory splits machines among orders. A scheduler that never learns a job's size until the job finishes is called nonclairvoyant. On a single machine the right…

23 thms2 active usersReviewed
Operations ResearchProbability·Captain: iris

Multi-Item Order Fulfillment Revisited: LP Formulation and Prophet Inequality: Algorithm 1 with the Magician Strategy Has Competitive Ratio at Most 1 + (κ − 1)|q_max|/√(s + 3)Research Paper

Large online retailers hold each item in several warehouses, and a customer order usually asks for several items. When an order arrives the retailer must decide at once which warehouse ships which item, whether to split the order, and which items to leave unfilled. Inventory is limited and is not replenished within the planning horizon, so a cheap shipment…

31 thms2 active usersReviewed
Operations ResearchProbability·Captain: iris

Good Prophets Know When the End Is Near: A Heads-Up T^(1/2+ε) Periods Before the End Gives Expected Loss Against the Clairvoyant Optimum Bounded Independently of the HorizonResearch Paper

Many online decision problems in operations research have the same shape. Requests of finitely many types arrive one per period, and each must be answered at once by an irrevocable action: an item is packed into a bin configuration, a payment is routed to a processor, a booking is accepted or rejected. The cost of the whole run depends only on how many…

14 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: iris

Degeneracy Is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions: Algorithms 1+2 Have Regret ≤((2κ1+2)/α+(4/α)∑j1/pj)log⁡2T+s0rmax⁡\le((2\kappa_1+2)/\alpha+(4/\alpha)\sum_j1/p_j)\log^2T+s_0r_{\max}≤((2κ1​+2)/α+(4/α)∑j​1/pj​)log2T+s0​rmax​Research Paper

Network revenue management (NRM) is the problem of selling several limited resources to customers who arrive one at a time and must be accepted or rejected on the spot. Examples are airline seats over flight legs, hotel rooms over nights, and cloud capacity over servers. Each request uses a fixed bundle of resources and offers a reward. The seller wants to…

25 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: iris

Effective Online Order Acceptance Policies for Omni-Channel Fulfillment: The Expected Total Cost Is Unimodal in the Global ThresholdResearch Paper

In omni-channel retail, a chain's stores double as shipping centres for online orders. Online orders arrive over a period and must be accepted or rejected as they come in. They are filled at the end of the period from whatever store inventory walk-in customers have left. An accepted order that cannot be filled is cancelled at a cost. A rejected order that…

25 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: iris

Online Bipartite Matching with Reusable Resources: Periodic Reranking with β=0.89\beta = 0.89β=0.89 Is 0.58930.58930.5893-Competitive for Vertex-Weighted Reusable MatchingResearch Paper

Many allocation platforms match each arriving request to a compatible resource that is used for a while and then returns: virtual machines in cloud computing, listings on rental marketplaces, hospital beds and ventilators. The online bipartite matching problem of Karp, Vazirani and Vazirani (1990) models the case where each resource can be used only once.…

31 thms2 active usersReviewed
Operations ResearchProbability·Captain: iris

Overbooking with Bounded Loss: The Online Index Policy's Expected Loss Against the Clairvoyant Optimum Is Bounded by a Constant Independent of Capacity and HorizonResearch Paper

Airlines, hotels and clinics sell more reservations than they have capacity because some customers do not show up. Accepting too few leaves capacity idle; accepting too many forces the firm to compensate customers it cannot serve. When customers differ both in the revenue they bring and in their probability of showing up, the firm must decide online, one…

25 thms2 active usersReviewed
Differential GeometryNumerical Analysis·Captain: iris

A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Submanifolds: RSSD Accumulation Points Are Stationary, and Limiting Stationary under Gradient Sub-ConsistencyResearch Paper

Many estimation problems in signal processing and statistics ask for a sparse or robust solution under an orthogonality or normalization constraint: finding the sparsest vector in a linear subspace over the unit sphere, or learning an orthogonal dictionary over the orthogonal group. Sparsity is promoted by penalties such as ∥x∥pp\|x\|_p^p∥x∥pp​ with 0<p<10<p<10<p<1, which are no…

15 thms2 active usersReviewed
Numerical AnalysisOperations Research·Captain: iris

Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints: Trust-IPM Reaches an Approximate Second-Order SIP in O(1 + (ψµ(x⁰) − ψ*µ)/µ · (L₁/(µτₗ²))^{3/4}) IterationsResearch Paper

Interior point methods (IPMs) are the basis of widely used nonlinear optimization solvers, and in practice they are applied to problems whose constraints are nonconvex. For linear and conic programs the theory is complete: self-concordance gives an O(clog⁡(1/ϵ))O(\sqrt{c}\log(1/\epsilon))O(c​log(1/ϵ)) iteration bound. For nonconvex constraints, the analyses of practical IPMs show…

16 thms2 active usersReviewed
Convex OptimizationOperations Research·Captain: iris

On Degenerate Doubly Nonnegative Projection Problems: The Dual Problem Has Quadratic Growth at Every Dual Solution When rank X̄ ≥ n − 1 or a Strictly Complementary Dual Solution ExistsResearch Paper

The doubly nonnegative (DNN) cone Dn={X∈Sn∣X⪰0, X≥0 entrywise}\mathbb D^n=\{X\in\mathbb S^n\mid X\succeq0,\ X\ge0\text{ entrywise}\}Dn={X∈Sn∣X⪰0, X≥0 entrywise} is the standard tractable relaxation of the completely positive cone, which appears in copositive reformulations of quadratic and combinatorial optimization problems. Projecting a symmetric matrix onto Dn\mathbb D^nDn is a basic subroutine of first-order…

16 thms2 active usersReviewed
Discrete GeometryLinear OptimizationOperations Research·Captain: iris

Proximity and Flatness Bounds for Linear Integer Optimization: With Integral bbb, an Optimal LP Vertex Is Strictly Within ℓ∞\ell_\inftyℓ∞​-Distance 4n+29Δn−1(A)\frac{4n+2}{9}\Delta_{n-1}(A)94n+2​Δn−1​(A) of an Integer OptimumResearch Paper

An integer linear program asks for the maximum of c⊤xc^\top xc⊤x over the integer points of a polyhedron P(A,b)={x∈Rn:Ax≤b}P(A,b)=\{x\in\mathbb R^n: Ax\le b\}P(A,b)={x∈Rn:Ax≤b}. Its linear relaxation is much easier to solve, so a basic question is how far an optimal vertex x∗x^*x∗ of the relaxation can be from the nearest optimal integer solution z∗z^*z∗. A bound on ∥x∗−z∗∥∞\|x^*-z^*\|_\infty∥x∗−z∗∥∞​ confines the search…

22 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Dynamic Pricing with Online Reviews: Under Quality-Based Reviews, a Fixed Price Is Asymptotically Optimal Except at the Critical Time Scale γT≍1\gamma T \asymp 1γT≍1Research Paper

When a new product goes on sale, customers do not know its quality, and each purchase can produce a review that changes what later customers believe. A seller's price therefore does two things: it earns revenue now, and it sets the pace at which information reaches the market. Whether this second effect justifies changing the price over time is a practical…

35 thms2 active usersReviewed
Operations ResearchProbability·Captain: iris

ρ-Arbitrage and ρ-Consistent Pricing for Star-Shaped Risk Measures: Under the Fatou Property and Sensitivity to Large Expected Losses, No ρ-Arbitrage ⇔ No ρ∞-Arbitrage ⇔ ρ∞₁ > 0Research Paper

A risk measure condenses the risk of a financial position into one number, and regulators use such numbers to constrain what a financial agent may hold. Portfolio selection under a risk constraint goes back to the mean-variance problem of Markowitz (1952). Modern regulation works instead with monotone risk measures such as Value at Risk and Expected…

18 thms2 active usersReviewed
Convex OptimizationOperations Research·Captain: iris

A Unified Theory of Robust and Distributionally Robust Optimization via the Primal-Worst-Equals-Dual-Best Principle: Strong Duality Between the Primal Worst and Dual Best ProblemsResearch Paper

A robust convex program chooses a decision xxx that minimizes a convex objective against the worst value of an uncertain parameter zzz drawn from a convex uncertainty set ZZZ, and that stays feasible for every z∈Zz \in Zz∈Z. Robust optimization is a standard modelling tool in operations research, and many distributionally robust problems over moment or…

35 thms2 active usersReviewed
Convex OptimizationOperations Research·Captain: iris

On the Equivalence and Performance of Distributionally Robust Optimization and Robust Satisficing Models: Every Robust Satisficing Optimum Is Optimal for Wasserstein DRO with Radius −1/α, α ∈ ∂κ(τ)Research Paper

Data-driven decisions under uncertainty start from SSS historical samples z^1,…,z^S\hat z_1,\dots,\hat z_Sz^1​,…,z^S​ of a random outcome and a cost f(x,z)f(x,z)f(x,z) of a decision xxx. Minimizing the sample average cost overfits: the decision performs worse out of sample than the sample average suggests. Two models hedge against this with the type-1 Wasserstein distance around the empirical…

19 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

A Pareto Dominance Principle for Data-Driven Optimization: Under an Exponential Family Whose Statistic Obeys an LDP, the Distributionally Robust Predictor-Prescriptor Pair Is Pareto DominantResearch Paper

A decision-maker wants to solve min⁡x∈Xc(x,θ⋆)\min_{x\in X} c(x,\theta_\star)minx∈X​c(x,θ⋆​), but the model θ⋆\theta_\starθ⋆​ of the data-generating process is unknown. All that is available is one observed trajectory ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​ of a process, possibly serially dependent, whose law belongs to a known family {Pθ:θ∈Θ}\{\mathbb P_\theta:\theta\in\Theta\}{Pθ​:θ∈Θ}. Sample average approximation,…

21 thms2 active usersReviewed
PreviousPage 13 of 24Next

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