Topics — What a work is about. Nucleation holds whatever reading the owner files here, whether or not an Anthology of the SOTA topic could also hold it; instruction for ML practice belongs to the anthology (ADR-048). The words are seeded from the clusters the reading-time triage of 2026-09-25 found, and grow by decision.
Operations research — optimization of real systems — routing, scheduling, facility location, combinatorial algorithms.
15 of 1352 THEORY documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| THEORY-332 v2 | For one index with no space limit, Bruno and Chaudhuri’s online tuner, which builds the index once the savings it would have given have risen by its build cost above their last low and drops it once they have fallen by the build cost below their last high, is not three-competitive: when every statement’s saving or loss is at most a fraction f of the build cost, a repeated workload makes it cost nearly 3 + 2f times the offline optimum, and one statement whose saving exceeds the build cost makes the ratio unbounded; no upper bound is shown | Bruno and Chaudhuri (2007), LIT-1095, read in NOTE-896. An always-on index tuner keeps, per index, the running sum of what each statement would have saved (updates counting as losses) and creates or drops the index when that sum moves by the build cost from its last extreme. The paper calls the single-index rule three-competitive, but its proof is one workload on which the ratio approaches 3, a lower bound. The reading’s own check found ratios up to 4.7 when one statement’s saving is near the build cost, and an unbounded ratio when it exceeds it; with every saving at most a tenth of the build cost no random workload passed 2.4, but a constructed one with steps at most fB approaches 3 + 2f (note of 2026-10-20). The multi-index tuner with a space limit is heuristic, and all costs are optimizer estimates. | Active |
| THEORY-345 | Choosing indexes for a known mix of queries and updates, to minimize query cost plus a per-index upkeep, is NP-hard as the number of attributes and query types grows, and the tools built for it choose one stored order and a set of secondary indexes per table by searching configurations costed with the query optimizer’s own estimates, optimal at best relative to those estimates, with no proved guarantee for their heuristics and no term for the one-time cost of building | Piatetsky-Shapiro (1983), LIT-1089, read in NOTE-902; Finkelstein, Schkolnick and Tiberio (1988), LIT-1084, read in NOTE-898; Chaudhuri and Narasayya (1997), LIT-1083, read in NOTE-900. Minimum set cover reduces to choosing single-attribute secondary indexes under a known workload with a fixed upkeep per index. DBDSGN chooses the one clustered order and the secondary indexes per table against a frequency-weighted sum of access, update and upkeep costs plus storage, read from the System R optimizer; AutoAdmin picks at most k indexes by greedy search over what-if indexes. The model is steady state over a fixed workload: it prices upkeep against per-query savings, not a one-off build or sort against later lookups, and its optimality is relative to the optimizer’s estimates, never to measured execution. | Active |
| THEORY-350 | Under a budget on maintenance time, a stored view’s upkeep depends on which other views are stored, so upkeep is not additive and adding a view can lower it, and greedily adding the single view of best saving per unit of upkeep can be arbitrarily bad; on OR view graphs a greedy over inverted tree sets gets 1 − 1/e of the saving of an optimum given as much upkeep, using up to twice the budget, if no tree-piece of the optimum alone exceeds the budget | Gupta and Mumick (1999), LIT-1092, read in NOTE-890, with the proofs of the journal version (2005), LIT-1080, read in NOTE-901, and the superadditivity first noted by Gupta (1997), LIT-1091, read in NOTE-889. Minimizing query cost subject to a cap on total maintenance time, one stored view can make another cheaper to keep current, so saving per unit of upkeep is not monotone and single-view greedy fails without bound (Example 2). Grouping views into inverted tree sets restores a 1 − 1/e guarantee, proved in 2005 (Theorem 8), for OR view graphs only, bicriteria, under an assumption on the optimum, with greedy stages exponential in general. The proof does not treat the negative effective costs the paper allows. Upkeep is a budget, not a cost traded against savings, and staleness and build cost are not modelled. | Active |
| THEORY-356 | When stored views are never updated, greedily storing the view of largest marginal saving in query cost gets at least 1 − 1/e of the optimal saving on a data-cube lattice or any OR or AND view graph, against the optimum for the same number of views or for the space the greedy ends up using, which may exceed the budget by one view | Harinarayan, Rajaraman and Ullman (1996), LIT-1094, read in NOTE-895; Gupta (1997), LIT-1091, read in NOTE-889; Gupta and Mumick (2005), LIT-1080, read in NOTE-901. A stored answer is worth the saving on every query derivable from it, less what answers already stored save, and greedy on that marginal saving gets 1 − ((k−1)/k)^k ≥ 1 − 1/e of the best saving for k views; under a space budget the same holds against the optimum in the space the greedy actually uses (up to one view over), or 0.63 − f when no view takes more than a fraction f of the budget. The bound is on saving against storing the base view alone, not on query cost, and it holds only with no updates: once upkeep enters the objective it is proved only for AND graphs in which every view is queried more often than it is updated. | Active |
| THEORY-364 | When each cached value is an interval its source guarantees to contain the current value, and a query must return an answer interval no wider than R whatever the true values, choosing the cheapest set of exact reads for a SUM is a 0/1 knapsack problem, NP-complete in general and solved by taking the narrowest intervals first when read costs are equal, and for a COUNT with a selection predicate the cheapest choice is the ⌈|T?| − R⌉ cheapest undecided tuples | Olston and Widom (2000), LIT-1117, read in NOTE-922. In TRAPP a cache holds intervals that sources keep valid by pushing a refresh whenever a value escapes, and each query names a width R its answer may have. The SUM answer is the sum of the intervals, so meeting R at least read cost is knapsack (profit = read cost, weight = width, capacity = R); COUNT under a predicate has a greedy optimum. Staleness becomes bounded imprecision, never error, and only the query-time cost of buying it down is optimized: the sources’ upkeep, the choice of interval widths and any cost of imprecision are outside the model. The MIN rule’s optimality proof is in an unread technical report. | Active |
| THEORY-375 v2 | In one simulator evicting whole query-shaped cache regions, no replacement value function was best on every workload: a value based on distance from the current query beat LRU where queries clustered around a hot region or wandered with loops, while MRU was best on regular cyclic paths, by up to 2.3 times over the distance value and 9.6 times over LRU; none of the functions weighs what a region would cost to fetch again, and nothing is proved | Dar, Franklin, Jónsson, Srivastava and Tan (1996), LIT-1113, read in NOTE-904. With semantic regions as the unit of eviction, Manhattan distance from the most recent query beat LRU at every query size on a skewed selection workload, and a directional variant was best or tied on random map paths (LRU within 1.06) and on lollipop paths circling a square five or more times; MRU won on a single circuit and on plain squares (Manhattan 2.29 and LRU 9.57 on the 32 × 32 square). The study is simulation only, with synthetic paths and no refetch cost in any value; it shows that the best forecast of reuse depends on the workload, not that semantic distance is a robust rule. | Active |
| THEORY-377 v2 | In Olston, Loo and Widom’s simulations, a rule that multiplies a cached interval’s width by 1 + α on a pushed refresh with probability min{ρ, 1}, and divides it by 1 + α on a query’s exact fetch with probability min{1/ρ, 1}, settled within 1% of the best fixed width on one random walk and within 5% over eight walk settings; on a 50-host network-traffic trace, restricted to exact copies, it almost matched a tuned adaptive cache-or-not rule, and with a 50-value cache, where queries tolerated imprecision, it cost less; that it converges to the best width is argued, not proved | Olston, Loo and Widom (2001), LIT-1109, read in NOTE-912. The rule treats a pushed refresh as “too narrow” and a fetch as “too wide”, weighted by ρ = 2C_vr/C_qr, and needs no measurement of update rates, query rates or precision demands. Within 1% of the best fixed width on one random walk and within 5% over eight settings; with α = 1 and thresholds it tracked a 50-host traffic trace. With every copy forced exact it decided cache-or-not as well as an adaptive exact-caching rule, and did better where imprecision was allowed, except with a small cache. Convergence is argued from the balance condition only, all evidence is the authors’ simulation, and there is no worst-case guarantee. | Active |
| THEORY-378 | When items change as independent Poisson processes with known rates and a fixed total refresh rate is shared among them, refreshing every item equally keeps the copy at least as fresh and at most as old, averaged over time, as refreshing in proportion to change rate, for any spread of rates; the freshness-optimal share rises and then falls with change rate and gives nothing to items that change too fast for the budget | Cho and Garcia-Molina (2000), LIT-1119, read in NOTE-906. Freshness is the fraction of items equal to their source, age the mean time since an unseen change, both averaged over time and over equally weighted items. With fixed-interval refresh, uniform refresh is never worse than proportional on either measure, by convexity (proof in the authors’ technical report). Under a fixed budget the freshness-optimal allocation starves the fastest-changing items; the age-optimal one refreshes them somewhat more. It prices staleness as an objective under a fixed budget: there are no reads, no query savings, no build cost and no cost of a stale use, so it is a staleness term and not a model trading staleness against upkeep. | Active |
| THEORY-382 v2 | When a web server keeps each page fragment either cached and invalidated by updates or stored and refreshed after them, materializing trades staleness for response time, and in one synthetic simulation with fixed costs a periodic greedy that moves a capped number of fragments between the two, to keep the share of fresh fragments served above a set threshold, tracked that threshold by the authors’ reading of its curves, answered faster than caching alone and recovered from overload by materializing everything; no bound on its distance from the best plan is shown | Labrinidis and Roussopoulos (2003), LIT-1105, read in NOTE-911. Quality of Data is the share of fresh fragments in served pages; OVIS(θ) estimates per fragment the change in response time (hits and misses against refresh load) and in QoD from switching policy, and each period greedily switches up to MAX_CHANGE fragments to spend a QoD surplus on speed or buy back a deficit. The paper asserts the greedy step is best under the cap and proves nothing; the evidence is one simulator with uniform costs and no comparison with an optimum. The reading the evidence does not support: that this is a joint cost model of build, upkeep, staleness and savings. Staleness is a user-set threshold, not a price, and switching and storage are free. | Active |
| THEORY-383 v2 | On one Apache and Informix server answering cheap indexed selections over 1000 pages, a page whose query result was stored in the DBMS and refreshed on every update answered more slowly than one recomputed on each request at five or more updates per second, which the authors explain by reading the stored result costing about as much as recomputing it and its refresh loading the same DBMS, while a finished page stored at the web server and rewritten on every update answered 10 to 230 times faster than either | Labrinidis and Roussopoulos (2000), LIT-1118, read in NOTE-908. Three ways to serve a database-generated page under online updates, with no stale reads allowed: compute on request, store the query result in the DBMS, or store the finished page at the web server. A cost model sums access and update costs by frequency; the per-page selection problem is stated and not solved. On their testbed the page stored at the web server won at every load, and the result stored in the DBMS lost to recomputation at five or more updates per second. The reading the evidence does not support: that storing an answer pays whenever it is reused enough. Where it is stored decided the outcome, and the generalization to other systems is the authors’ expectation, not a measurement. | Active |
| THEORY-386 | When a cached interval of width W is kept valid by its source, which pushes a refresh at cost C_vr whenever the value leaves it, and queries fetch the exact value at cost C_qr whenever it is too wide, and the chances of the two per step go as 1/W² and as W, the expected refresh cost is least at W* = (ρK₁/K₂)^(1/3) with ρ = 2C_vr/C_qr, where ρ times the chance of a pushed refresh equals the chance of a fetch | Olston, Loo and Widom (2001), LIT-1109, read in NOTE-912. The cost rate Ω(W) = C_vr·K₁/W² + C_qr·K₂·W is least where ρ·P_vr = P_qr. The minimum is calculus on assumed forms. P_qr ∝ W follows exactly from uniform precision demands; P_vr ∝ 1/W² comes from a Chebyshev bound on a random walk used as an estimate, and the paper’s simulation of a random walk measured both proportionalities. Staleness here is priced as refresh traffic: the source guarantees validity, so a stale read is imprecise but never wrong, and there is no build cost and no cost of a wrong or imprecise answer. | Active |
| THEORY-501 | In weekly waste collection where each point’s visit days are free and its bin capacity must cover the longest gap between visits, a genetic algorithm that searches visit schedules and derives bins from them builds routes about 6% cheaper than eight-hour Gurobi incumbents but buys about 20% more bin capacity, ending level on overall cost at its best of 30 runs and 4–6% worse on a typical run, on five 12-point instances where the incumbents’ own optimality gaps are 26–32% | González et al. (2025), LIT-008, read in NOTE-015. The comparison is against incumbents whose distance from optimum is unknown, on five 12-point random subsets of one real instance, one of which was also used to tune the GA. Best of 30 against the MILP: −0.08% overall; against the MIQP: +1.70%; the GA’s mean or median is +3.75% and +5.61%. The abstract’s “able to match the results of exact solvers” says less than it appears to. On 40–163 points there is no bound or baseline. | Active |
| THEORY-654 | For full-state linear-quadratic regulation of a single-input plant, the return-difference identity keeps the sensitivity at or below 1 at every frequency, so the loop tolerates any gain increase, a gain cut to one half and at least 60° of phase error for any Q ≥ 0 and r > 0; the guarantee does not carry over when the state is replaced by an observer’s estimate | Başar, Meyn & Perkins (2020), LIT-051, graduate course notes read in full in NOTE-062, with every worked example recomputed. §10.6 derives |1 + L(jω)|² = 1 + |P(jω)|²/r ≥ 1 for the full-state loop, hence |S| ≤ 1 and the classical margins. The derivation is for one input; the multi-input version needs more, which the notes do not discuss. The Pendubot thread shows a controllable, observable plant whose one-sensor observer-based design has gain margin below 10⁻². The result is Kalman’s and standard; the notes are an adequate free citation for it. | Active |
| THEORY-668 | When the encoder is restricted to prunings of one fixed hierarchy of nested partitions, any non-negatively weighted sum of relevant information, irrelevant information and compression decomposes into per-node terms, so a bottom-up recursion finds the unique optimal tree with fewest leaves exactly in linear time, while greedy top-down splitting can miss information lying below a level that carries none; penalising irrelevant information only prunes the information-bottleneck tree | Larsson, Maity & Tsiotras (2022), LIT-868, read in full in NOTE-676, every proof followed step by step. The decomposition is the chain rule for refinements, and the recursion is the classic bottom-up pruning of a fixed tree. NOTE-676 declined a THEORY as exact but narrow; it is filed because the reading supports it as stated and its greedy-failure point bears on how hierarchy is measured. The hierarchy is given, not found, and the evaluation is one image. | Active |
| THEORY-1303 | For an uncertain linear program, a decision fixed before the data are revealed must satisfy every realization at once (the robust counterpart, ∃ solution ∀ data), while a decision that may adjust after them need only have a feasible adjustment for each (the adjustable robust counterpart, ∀ data ∃ adjustment); the second is never more conservative and can be feasible where the first is not, the two coincide when each constraint’s uncertainty is its own, and decisions may be restricted between them by what part of the data they read or by the form of the rule | Ben-Tal, Goryashko, Guslitzer and Nemirovski (2004), LIT-1975, read in NOTE-1503. Active: the definitions, the two worked examples (checked by hand), Theorem 2.1 and its proof, and the reported inventory results with their sizes. It does not say the information-basis case is solved in general (the paper asserts it extends), nor that affine rules lose nothing. | Active |