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
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 4: First-Fit Decreasing Uses at Most 71/60 L* + 5 Bins When No Item Exceeds 1/2Research Paper

Bin packing asks how to place a list of items with sizes in (0,1](0,1](0,1] into as few unit-capacity bins as possible. It models the cutting of stock material, the packing of files onto tracks of a disc and the assignment of jobs to machines with a common deadline. Deciding the optimum is NP-hard, so in practice simple rules are used, and the question is how far…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 2: First-Fit and Best-Fit with Bounded Item SizesResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models cutting stock, memory allocation, file placement and the loading of trucks, and it is NP-hard, so in practice lists are packed by simple rules that look at one item at a time. The two most widely used rules are First-Fit and Best-Fit, and the question that…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 1: First-Fit and Best-Fit Have Asymptotic Worst-Case Ratio 17/10Research Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It is one of the first problems studied through the worst-case analysis of approximation algorithms, and it models storage allocation, paging and file placement on tracks, as well as cutting-stock problems in operations research. Deciding the optimum exactly is NP-hard,…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written 1∣rj∣∑Cj1|r_j|\sum C_j1∣rj​∣∑Cj​), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…

9 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework II: Margin-Based Generalization Bound for the SPO Loss under the Strength PropertyResearch Paper

In the predict-then-optimize paradigm a model first predicts the cost vector of a linear optimization problem from contextual features, and the prediction is then fed to an optimization solver that returns a decision. Examples include routing with predicted travel times and portfolio choice with predicted returns. The quality of a prediction is judged by…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems III: Add-Drop-Swap Local Search for Uncapacitated Facility Location Has Locality Gap 3Research Paper

The uncapacitated facility location (UFL) problem is one of the basic models of location theory and operations research: a firm chooses which warehouses, plants or servers to open, paying a fixed cost for each open site and a service cost for every client according to its distance to the nearest open site. It is also a standard test case for approximation…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: naimengye

Understanding Machine Learning XV: Neural NetworksTextbook

A feedforward neural network is a directed acyclic graph of neurons, each computing a fixed scalar activation of a weighted sum of its inputs; fixing the graph and the activation and letting the weights vary gives a hypothesis class. Chapter 20 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO97811072…

8 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: naimengye

Multi-armed Bandit Allocation Indices I: The Gittins Index, Optimal Stopping and MonotonicityTextbook

A decision-maker has nnn projects, each a Markov reward process, and at every decision time may advance exactly one of them; the others stay frozen. Which project to advance so as to maximize the expected total discounted reward? Posed as a dynamic program the problem has a state space that is the product of the nnn state spaces, and the size of that product…

12 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

The Theory and Practice of Revenue Management II: OverbookingTextbook

Every airline, hotel and car-rental firm sells more reservations than it has capacity, because some customers cancel or do not show. Chapter 4 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) is the theory of that decision. Its static models pick one overbooking limit from the show distribution; its dynamic model, a…

8 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

The Theory and Practice of Revenue Management I: Single-Resource Capacity ControlTextbook

An airline sells one flight, a hotel one night, a car-rental firm one day of one car: a fixed capacity, perishable at a deadline, sold to customers who arrive over time and are willing to pay different amounts. Chapter 2 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) is the theory of that single resource. Its three models…

11 thms4 active usersReviewed
🏆Completed
Control TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Resource Allocation and Cross-Layer Control in Wireless Networks I: The Network Layer Capacity RegionTextbook

Every wireless network control algorithm — routing, scheduling, power control, admission control — is ultimately judged against one question: which traffic loads can it keep stable? Answering that question requires a precise, algorithm-independent notion of queueing stability under random arrivals and a randomly time-varying, possibly non-ergodic-looking…

8 thms4 active users
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization IV: Regularization by Robustification in Classification and RegressionTextbook

Regularization — adding a penalty on model complexity to an empirical risk minimization objective — is one of the oldest and most reliably effective tools in statistical learning: ridge regression, LASSO, and margin-based support vector machines all fit this template. For decades the regularization weight and penalty function were chosen heuristically or by…

15 thms4 active users
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning VII: Gradient Sliding for Composite OptimizationTextbook

Composite convex programs — objectives split into a smooth piece and a nonsmooth piece — are ubiquitous in data analysis: LASSO-type inverse problems, regularized empirical-risk minimization, and total-variation-type image reconstruction all minimize f(x)+h(x)+χ(x)f(x)+h(x)+\chi(x)f(x)+h(x)+χ(x) over a convex set, where fff is smooth (a data-fidelity term, often expensive to…

5 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning III: Stochastic Mirror DescentTextbook

Machine learning's canonical training objective — minimize an expected or empirical risk over a data distribution — is almost never observed exactly: at each step an algorithm sees only a noisy gradient sample (a minibatch gradient, a single-example gradient, a simulation draw). Stochastic mirror descent (Nemirovski, Juditsky, Lan & Shapiro 2009) is the…

5 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization XIII: Blackwell's Approachability Theorem and Online Convex OptimizationTextbook

Von Neumann's minimax theorem (Chapter VIII) settles two-player zero-sum games with scalar payoffs. In 1956, Blackwell asked the natural generalization: what can a player guarantee in a repeated game with vector-valued payoffs, where "winning" means driving the average payoff into a target set rather than above a target value? For decades the resulting…

12 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization XII: The Online Boosting MethodTextbook

Chapter XI boosted a weak learner into a strong one for a single offline fit to a fixed sample. Chapter 12 asks the analogous question online: when the pool of experts is too large to run Hedge over directly (the contextual-learning setting, where "experts" are policies mapping contexts to actions and their number is exponential), can black-box access to a…

12 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization IX: From Online Convex Optimization to PAC LearningTextbook

Every algorithm in Chapters I–VIII minimizes regret, an online, adversarial performance measure with no reference to a data-generating distribution. Chapter 9 asks what regret minimization buys in the classical statistical learning setting, where examples are drawn i.i.d. from a fixed distribution and the goal is a hypothesis that generalizes well to unseen…

7 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization VII: The Online Conditional Gradient AlgorithmTextbook

Every algorithm through Chapter VI updates its iterate by a Euclidean projection onto the decision set KKK. For many decision sets that arise in practice — bounded-nuclear-norm matrices (matrix completion / recommendation systems), the flow polytope (network routing), the Birkhoff–von Neumann polytope (ranking/permutations), matroid polytopes — a projection…

10 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization IV: The Online Newton Step AlgorithmTextbook

Online convex optimization measures a decision maker against the best fixed decision in hindsight, and the standard guarantee — achieved, for instance, by online gradient descent — is regret growing like O(T)O(\sqrt T)O(T​) over TTT rounds. This rate is unimprovable for general convex losses: an adversary can always force Ω(T)\Omega(\sqrt T)Ω(T​) regret against any algorithm.…

13 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization X: Efficient Adaptive Regret for Online Convex OptimizationTextbook

Every regret guarantee through Chapter IX compares the algorithm to the single best fixed decision in hindsight. That comparison is meaningless when the environment itself changes: a commuter's best route differs on weekdays versus weekends, an investor's best portfolio differs in a bull versus a bear market. A standard sublinear-regret algorithm, competing…

9 thms4 active users
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Supermodularity and Complementarity V: Existence of Equilibrium in Supermodular GamesTextbook

Existence of equilibrium is the first question any model of strategic interaction must answer, and the classical answer — Nash's theorem via Kakutani's fixed point theorem — asks for a convex, compact strategy space and continuous payoffs. Many of the models economists actually use do not have that: a firm's technology set can be discrete or irregular, and…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization III: Online Gradient DescentTextbook

Online convex optimization (OCO) models a repeated decision process: at each round a learner picks a point in a convex set, an adversary (or the world) reveals a convex cost function, the learner pays that cost at its own point, and the process repeats. No statistical assumption on the sequence of costs is made. This model, introduced by Zinkevich…

8 thms4 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization I: Learning from Expert Advice and the Hedge AlgorithmTextbook

Consider a decision maker who must choose, at each of TTT rounds, between two actions on the advice of NNN "experts," none of which is known in advance to be reliable. This is the prediction-from-expert-advice problem, introduced by Littlestone and Warmuth [Littlestone & Warmuth, The Weighted Majority Algorithm, FOCS 1989/Inf. Comput. 1994] and generalized to…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Introduction to Stochastic Programming VI: Jensen and Edmundson-Madansky BoundsTextbook

Two-stage stochastic programs with recourse require evaluating Q(x)=Eξ[Q(x,ξ)]Q(x) = \mathbb E_\xi[Q(x,\xi)]Q(x)=Eξ​[Q(x,ξ)], the expected value of a recourse function, at every candidate first-stage decision xxx. When ξ\xiξ is high-dimensional or continuously distributed, this expectation is a multivariate integral of a piecewise-linear, generally nondifferentiable integrand, and classical…

8 thms4 active users
PreviousPage 18 of 70Next

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