Smale's Ninth Problem: Strongly Polynomial Linear ProgrammingOpen Problem
The linear feasibility problem takes a matrix and a vector and asks whether the system of linear inequalities in real unknowns
3,614 missions · 2,642 completed
The discipline of applying mathematical analysis to complex decision problems in operations: allocating scarce resources, scheduling, routing, inventory, and the design of service and production systems. Drawing on mathematical programming, stochastic modeling, queueing, simulation, and game-theoretic reasoning, it seeks policies that perform provably well in systems shaped by constraints, congestion, and uncertainty.
The linear feasibility problem takes a matrix and a vector and asks whether the system of linear inequalities in real unknowns
Why do interior-point methods solve convex programs in Newton steps? Nesterov and Nemirovskii's answer is self-concordance: a convex function whose third derivative is controlled by its second, along every line, admits a Newton analysis with absolute constants and no condition number —…
The final step from bandits to reinforcement learning: actions now change the state of the world. Chapter 38 of Lattimore–Szepesvári studies online learning in an unknown Markov decision process with states, actions and rewards in . The optimism principle of Mission II scales up: UCRL2 maintains confidence sets over transition kernels, solves an ext…
How well can any algorithm possibly do? Chapters 13–17 of Lattimore–Szepesvári answer with three matching impossibility results. The divergence decomposition identifies the information a policy collects: . Feeding it into the Bretagnolle–Huber inequality of Mission VI…
Adaptive policies — recommendation systems, dynamic pricing rules, treatment protocols, trading strategies — choose actions based on the state they observe. A natural audit question is how much of a policy's performance comes from that adaptivity, as opposed to the average mix of actions it plays. Answering it requires a benchmark that plays the same…
A coverage system can assign demand points to facilities with different service radii. The minimum sum-of-radii objective measures the sum of those radii rather than the largest radius or the total distance to facilities. Its optimization problem fixes the number of clusters, so making one cluster cheaper can compensate for making another more expensive.…
A spanning tree is a set of network edges that connects every vertex and loses that property when any selected edge is removed. Transferring a spanning tree to another operator can leave the original network disconnected. The question studied here is how much connectivity must be sacrificed when the tree is chosen carefully. The paper gives a…
Exact Euclidean k-means asks for the least possible sum of squared distances from data points to freely located centers. Two parameters shape the problem: the number of centers, k, and the ambient dimension, d. An algorithm whose exponent depends on their product can be polynomial for every fixed pair and still become impractical as either parameter grows.…
An online decision maker often receives a summary of uncertain inputs before seeing their realized values. The secretary problem isolates one consequence of incomplete information: items arrive one at a time, and a rejected item cannot be recalled. The objective is to select a largest item. The question here is how much the entire sequence of exact moments…
A pinwheel instance asks whether a single machine, doing one task per day, can visit each task often enough that task occurs in every window of consecutive days. The problem models periodic servicing such as the perpetual maintenance of machines (arXiv:2202.01567), and its central question is how much of the machine's capacity can be promised in…
Integer programming solvers expose parameters, and in practice they are run on many instances of one application. Data-driven algorithm configuration asks for parameters that perform well on a training set of instances. For cutting planes, Balcan, Prasad, Sandholm and Vitercik (2021) bound the sample complexity of tuning Chvátal–Gomory cuts: how many…
In a network design game each user must connect a source to a destination in a shared network, and the cost of every link that is built is split among the users who route through it. A central planner would pick the routing of least total cost; the users instead pick routes that minimize their own payment, and the two goals can disagree. The price of…
Ride-hailing platforms, online labour marketplaces, organ-allocation systems and quantum switches all match two sides of a market whose agents do not wait forever. The standard abstraction is a bipartite queueing system: agents of finitely many types arrive over time, the platform decides which compatible pairs to match, and an unmatched agent leaves when…
Precedence-constrained scheduling takes a partial order on tasks as input, yet in practice the order is rarely known with full confidence. In product design, assembly, project scheduling and construction, the relation between two tasks is often not documented, and an expert must be consulted to determine it. For automotive assembly, probing direct…
In bin packing, items with sizes in must be partitioned into bins of total size at most one, using as few bins as possible; is that minimum. The problem is strongly NP-hard even in the 3-partition regime, where every size lies in and a bin holds at most three items, so research has concentrated on additive guarantees …
The pancake problem was posed in 1975: a stack of pancakes of distinct sizes is to be sorted, smallest on top, by repeatedly inserting a spatula and flipping the pancakes above it. Mathematically the stack is a permutation of and a move is a prefix reversal. Two questions arise: the diameter of the resulting pancake network (t…
In a complete market every contingent claim has one arbitrage-free price, the cost of replicating it. When part of the risk sits in an asset that cannot be traded, replication fails and arbitrage arguments leave an interval of prices. Indifference pricing selects a price from the seller's preferences: the price at which an investor with a given utility…
Every portfolio problem in discrete-time mathematical finance starts from a market model and asks two questions: is the market free of arbitrage, and does an investor with a given utility function have an optimal portfolio? The two questions are linked. If a riskless strategy with a chance of gain exists, an investor with strictly increasing utility can…
Sequential decisions under uncertainty appear in inventory control, portfolio choice, consumption planning and optimal stopping. The common model is the Markov Decision Model: a controller observes a state, picks an action, collects a reward, and the system moves at random to a new state. The standard solution method, backward induction, goes back to…
Mean-variance portfolio selection, introduced by Markowitz in 1952 (and slightly earlier by de Finetti), measures the risk of a portfolio by the variance of its return: among all portfolios that reach at least a prescribed expected return, choose one of smallest variance. The single-period problem was solved in the 1950s and is still the standard tool of…
An online retailer that holds inventory in many fulfillment centres (FCs) decides, for each item of an order, where to ship it from. A linear program solved over all orders gives, for each item, a probability distribution over FCs that is right on average. The difficulty is correlation: items sent to different FCs ship in separate packages, so an order is…
An impact investor ranks assets by an observable impact factor (an ESG score, a carbon intensity) and puts weight on the asset whose score ranks -th. What the portfolio earns is then driven by the vector of induced order statistics (also called concomitants) : is the residual…
In Bandits with Knapsacks (BwK) a player repeatedly picks one of actions; each choice yields a reward and consumes limited resources, and play stops as soon as a budget runs out. The model covers dynamic pricing with limited inventory, ad auctions with a spending cap and crowdsourcing with a payment budget (Badanidiyuru, Kleinberg, Slivkins 2018). Its…
Binary classification, multi-label classification and rank correlation estimation all score a model by counting the samples on which a linear score has the wrong sign. The natural penalty is the zero-one loss, which is on positive numbers and on the rest. Support vector machines, multi-label classification and the maximum rank correlation estimator are…
No-regret algorithms such as multiplicative weights and online mirror descent are the standard model of learning agents in repeated games. A classical fact is that when two such agents play a zero-sum game, the time-average of their mixed strategies converges to a Nash equilibrium (Freund and Schapire, 1999), and in general games the average play converges…