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
CombinatoricsOperations Research·Captain: iris

Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps: The de Klerk–Sotirov SDP Has Integrality Gap at Least z for Every z ∈ ℕResearch Paper

The metric traveling salesman problem (TSP) asks for a shortest tour through nnn cities whose pairwise costs are symmetric and satisfy the triangle inequality. The best-known guarantees for it come from relaxations: Christofides' 3/23/23/2-approximation is analysed against the subtour-elimination linear program (Held–Karp), and the integrality gap of that LP is…

37 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: iris

Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems: Discrete Gradient Descent Finds the Best Dock Allocation at Every Dock-Move DistanceResearch Paper

Bike-sharing systems such as New York's Citi Bike place bikes in docks at fixed stations. Over a day, demand pushes bikes away from some stations and toward others, and customers who find no bike, or no empty dock to return one, leave dissatisfied. Operators rebalance bikes by truck overnight, but the number of docks at each station is a strategic decision…

32 thms3 active usersReviewed
Linear OptimizationOperations Research·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation X: multiple simple recourse reduces to simple recourse with a mixed distributionTextbook

In a two-stage stochastic linear program, a simple recourse constraint penalizes the gap between a first-stage quantity zzz (for example a production level tTxt^{\mathrm T}xtTx) and a random demand ξ~\tilde\xiξ~​ at constant unit costs: a surplus z>ξ~z>\tilde\xiz>ξ~​ costs β\betaβ per unit and a shortage z<ξ~z<\tilde\xiz<ξ~​ costs α\alphaα per unit. Its expected cost has a closed form in the…

21 thms3 active usersReviewed
Operations ResearchProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation III: separate chance constraints under a multivariate normal distribution are convex for levels at least one halfTextbook

A linear constraint ηTx≥ξ\eta^{\mathsf T}x\ge\xiηTx≥ξ whose coefficients η\etaη and right-hand side ξ\xiξ are random cannot be required to hold for every realization without becoming either infeasible or very conservative. The chance-constrained (probabilistic) approach of Charnes and Cooper asks instead that it hold with a prescribed probability α\alphaα. Whether the…

20 thms3 active usersReviewed
Algebraic TopologyLinear algebra·Captain: iris

Hidden Convexity, Optimization, and Algorithms on Rotation Matrices: Every Linear Image of SO(n)\mathrm{SO}(n)SO(n) in the Plane Is Convex for n≥3n \ge 3n≥3Research Paper

Many problems in computer vision, robotics, satellite attitude estimation and point-cloud registration ask for the rotation that best explains some data. In matrix form they are linear optimization problems over the special orthogonal group, max⁡{⟨A,X⟩:X∈SO(n)}\max\{\langle A,X\rangle : X\in\mathrm{SO}(n)\}max{⟨A,X⟩:X∈SO(n)}, where ⟨A,X⟩=tr⁡(A⊤X)\langle A,X\rangle=\operatorname{tr}(A^\top X)⟨A,X⟩=tr(A⊤X). Without side…

13 thms3 active usersReviewed
Convex OptimizationOperations Research·Captain: iris

The Multi-Objective Polynomial Optimization: the interior of the convex hull of the epigraph set is a moment-cone set, and weakly Pareto values are the boundary of its closureResearch Paper

A multi-objective optimization problem minimizes several objective functions over one feasible set. The objectives rarely share a minimizer, so the usual targets are Pareto points, where no objective can be improved without worsening another, and weakly Pareto points, where the objectives cannot all be improved at once. Such problems arise in economics,…

20 thms3 active usersReviewed
Linear algebraOperations Research·Captain: iris

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: relaxation-based sampling is within slog⁡s+log⁡(ns)−slog⁡n+αs\log s+\log\binom{n}{s}-s\log n+\alphaslogs+log(sn​)−slogn+α of the optimumResearch Paper

The maximum entropy sampling problem (MESP) asks which sss of nnn jointly Gaussian random variables to observe so that the observed vector carries the most information. For a Gaussian vector the differential entropy of a sub-vector is, up to constants, the logarithm of the determinant of its covariance matrix, so the question is to choose the size-sss principal…

24 thms3 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

Blockchain-Enabled Deep-Tier Supply Chain Finance: Optimal direct financing and universal blockchain adoptionResearch Paper

A manufacturer can have ample cash while an upstream supplier lacks the funds needed to make production reliable. Financing that supplier through an intermediary changes both the cost of credit and the incentives to invest. Information is also uneven: a firm may know its immediate supplier's working capital without knowing the capital of a more distant…

17 thms3 active usersReviewed
Operations ResearchProbability·Captain: Shuze Chen

Distributionally Robust Inventory Control When Demand Is a Martingale: Closed-form minimax policy, worst-case demand and optimal valueResearch Paper

An inventory manager orders before seeing demand. Unsold stock incurs a holding cost, while unmet demand remains as a backlog and incurs a shortage cost. When the full demand distribution is unknown, a policy can be evaluated by its largest expected cost among distributions consistent with the available information. Dependence across periods matters because…

22 thms3 active usersReviewed
Operations ResearchStatistics·Captain: Shuze Chen

Technical Note—Joint Learning and Optimization of Multi-Product Pricing with Finite Resource Capacity and Unknown Demand Parameters: Rate-optimal regret of PSCResearch Paper

A seller offering several products often shares resources across those products. A room-night can support several travel packages; a seat can serve several itineraries. Selling one product changes what remains available for future customers. When the seller does not know how purchase probabilities respond to prices, each decision also determines what can be…

12 thms3 active usersReviewed
Control TheoryOperations ResearchPartial Differential Equations·Captain: mikedeng1

Hamilton-Jacobi Equations with Semilinear Costs and State Constraints, with Applications to Large Deviations in Games: Verification Theorem for the State-Constrained Target ProblemResearch Paper

Stochastic evolutionary game dynamics model a population of NNN agents who occasionally revise their actions by a noisy best-response rule with noise level η>0\eta>0η>0. As η→0\eta\to0η→0, the population spends long periods near Nash equilibria and occasionally transits between them; the exponential rates of these transitions, and hence which equilibrium is stochastically…

13 thms3 active usersReviewed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Improved Guarantees for the A Priori TSP: Random Sampling with Probability 1 − (1 − p)^0.663 and a 3/2-Approximate Master Tour Has Approximation Guarantee Below 3.1 on Instances with a DepotResearch Paper

In the a priori traveling salesman problem with independent activation, a tour through all customers must be fixed before it is known which customers need a visit; each customer is active independently with a known probability, and the fixed tour is afterwards cut short to the active ones. The model, introduced by Jaillet and by Bertsimas as the…

19 thms3 active usersReviewed
Convex OptimizationProbability·Captain: mikedeng1

Universal Barrier is n-Self-Concordant: The Universal Barrier of Every Proper Convex Domain in ℝⁿ Is an n-Self-Concordant BarrierResearch Paper

Interior-point methods minimize a linear function over a convex set K⊆RnK\subseteq\mathbb R^nK⊆Rn by following the minimizers of t cTx+φ(x)t\,c^{\mathsf T}x+\varphi(x)tcTx+φ(x), where φ\varphiφ is a self-concordant barrier for KKK. The number of Newton steps the path-following method needs to reach accuracy ϵ\epsilonϵ is O(νlog⁡(1/ϵ))O(\sqrt{\nu}\log(1/\epsilon))O(ν​log(1/ϵ)), where ν\nuν is the barrier's self-concord…

16 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: Shuze Chen

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties: Polynomial approximation for monotone submodular maximizationResearch Paper

Selecting a valuable subset subject to several simultaneous restrictions is a common combinatorial optimization problem. A facility may contribute less after nearby facilities have already been selected; a collection of observations may provide overlapping information. Such diminishing returns are captured by submodular objectives. Matroid constraints…

16 thms3 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Optimizing Quantum Circuit Parameters via SDP: Algorithm 1 Is a 0.562-Approximation for Quantum Max CutResearch Paper

Quantum Max Cut asks for the highest energy of a two-qubit interaction Hamiltonian placed on the edges of a weighted graph. It is a quantum analogue of Max Cut: a classical cut assigns one of two labels to each vertex, while a quantum state can use correlations and entanglement across the qubits. Lee studies an approximation algorithm that first solves a…

13 thms3 active usersReviewed
Convex OptimizationEconomics·Captain: mikedeng1

Discrete Choice Prox-Functions on the Simplex: The Convex Conjugate of an Additive Random Utility Surplus Function Is a Prox-Function on the SimplexResearch Paper

Prox-functions determine how subgradient and mirror-type optimization methods turn a direction of improvement into the next feasible point. On a probability simplex, that step should respect the geometry of probability vectors and be computable from the current direction. The entropic prox-function gives the softmax rule, familiar from the logit model of…

10 thms3 active usersReviewed
Mechanism DesignOperations Research·Captain: mikedeng1

The Important Role of Time Limits When Consumers Choose Their Time in Service: The Revenue-Maximizing IC and IR Mechanism Achieves the First Best and Imposes a Time Limit When Congestion Is HighResearch Paper

In many services the customer, not the provider, decides how long to stay: a gym session, a car-wash bay, an electric-vehicle charger, a call to a help line, a slot on a shared computing resource. Such services are called discretionary. Their congestion depends on how many customers join and on how long each of them stays. Providers manage them with per-use…

10 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models: The Sampled Upper Base-Stock Policy Costs at Most (1 + ε) Times the Optimum with Probability 1 − δResearch Paper

The periodic-review inventory problem asks how much stock to order in each of TTT periods when demand is random, unmet demand is backlogged, and both leftover stock and shortages are charged. When the demand distributions are known, a backward dynamic program computes an optimal policy, and the optimal policy is a base-stock policy: in each period, order up…

15 thms3 active usersReviewed
Machine Learning·Captain: mikedeng1

Suboptimal Local Minima Exist for Wide Neural Networks with Smooth Activations: For Generic Inputs and Any Depth and Width, Some Output Data Gives the Squared Loss a Sub-Optimal Local MinimumResearch Paper

Training a neural network means minimizing a non-convex loss over its weights. Local search methods can only certify local optimality, so a recurring question in the theory of neural network optimization is whether every local minimum of the training loss is a global minimum. A local minimum that is not global is called a sub-optimal (or bad) local minimum.

8 thms3 active usersReviewed
EconomicsOperations Research·Captain: mikedeng1

Non-Ownership Business Models for Solar Energy: When a Solar Power Company Optimally Offers Power Purchase Agreements, Leasing and SalesResearch Paper

Residential solar panels can reach customers through a purchase, a lease, or a power purchase agreement (PPA), under which the customer pays for the electricity the panels generate. These arrangements allocate panel ownership, subsidy receipts, and generation risk differently. A company choosing prices for all three therefore also chooses which customers…

12 thms3 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency: The Multiplicative Weight Algorithm Nearly Matches the Offline Dynamic Optimum's Work While Approximately Satisfying Every SLAResearch Paper

Cloud platforms divide a shared physical resource, such as a pool of processors, among many users at once. Each user is promised a service level agreement (SLA): a fraction β(i)\beta(i)β(i) of the resource that it should effectively receive whenever it has work to do. The operator wants two things that pull against each other: to keep the resource busy (total work…

29 thms3 active users
Operations Research·Captain: mikedeng1

Variational Analysis of Composite Models with Applications to Continuous Optimization: Fully Subamenable Functions Are Properly Twice Epi-Differentiable, with a Second Subderivative FormulaResearch Paper

A constrained optimization problem often has an objective of the form φ(x)=ϑ(f(x))\varphi(x)=\vartheta(f(x))φ(x)=ϑ(f(x)): a smooth map fff describes the model, while an extended-real function ϑ\varthetaϑ gives the cost and can assign +∞+\infty+∞ to infeasible outputs. Such a description covers polyhedral constraints, quadratic penalties on pieces, and many nonsmooth composite objectives.…

15 thms3 active usersReviewed
Complexity TheoryNumerical AnalysisQuantum Information·Captain: mikedeng1

Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation: an ε-Accurate Gradient of a Smooth Analytic Function from Õ(c√d/ε · log(d/δ)) Phase-Oracle QueriesResearch Paper

Many proposed quantum optimization and machine-learning methods (variational quantum eigensolvers, QAOA, quantum classifiers) tune the real parameters of a circuit by gradient descent on an objective f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R that is only accessible as a black box. Classically, a finite-difference estimate of ∇f\nabla f∇f costs on the order of ddd evaluations of fff…

14 thms3 active usersReviewed
Operations ResearchStochastic Systems·Captain: mikedeng1

Static Pricing: Universal Guarantees for Reusable Resources: Some Static Price Guarantees 15/19 of the Profit Rate, Market Share and Service Level of an Optimal Dynamic Pricing PolicyResearch Paper

Many services rent out a fixed stock of units that come back after use: hotel rooms, rental cars, cloud servers, hospital beds, parking spaces. Such reusable resources differ from perishable inventory because a unit sold now returns to the stock later, so the provider's pricing problem is a queueing control problem rather than a stock-depletion problem. A…

16 thms3 active users
EconomicsOperations Research·Captain: mikedeng1

Addictive Platforms 2: With Costly Addictive Technology, the Consumer Is Better Off under Joint-Profit Maximization than under Competition Exactly When the Cost Parameter Is HighResearch Paper

Digital platforms earn advertising revenue in proportion to the time users spend on them, and many of their design choices (infinite scroll, autoplay, notifications) raise engagement at the expense of the user's experience. Whether competition between platforms disciplines such addictive design or amplifies it is a question for competition policy and for…

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