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.
28 of 2004 LIT documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| LIT-008 v2 | Modeling and solving an integrated periodic vehicle routing and capacitated facility location problem in the context of solid waste collection | González et al. (2025), ARXIV-2504.10648. The paper couples bin-capacity choice with weekly periodic capacitated routing (Sunday off, cyclic). Service time depends on the chosen bin combination, which gives an MIQP; a Glover linearisation turns it into a MILP. It solves both with Gurobi 10 for 8 h, and also with a binary-mask + permutation GA (CX 0.8, EM 0.05, pop 100, 10,000 generations). On five 12-point instances Gurobi stops at 26–32% optimality gaps. The best-of-30 GA overall cost is on average −0.08% vs the MILP incumbent and +1.70% vs the MIQP incumbent; the GA mean or median is +3.75% and +5.61%. The GA routes better (−5.75% and −5.74% routing cost) but buys much more bin capacity (+19.88% and +22.59%). On 40–163-point Bahía Blanca instances the GA returns feasible solutions in 0.72–5.58 h per run, with no bound to compare against. | Active — read in full 2026-09-25 (NOTE-015); worth reading narrowly, for its formulation (Eqs. 1–2m, with the linearisation in 3a–5) and its public Bahía Blanca instances. The headline “GA matches exact solvers” should not be cited as a quality claim: the exact comparators are unproven incumbents with ~30% gaps, the GA was tuned on one of its five test instances, and the large instances have no reference at all. |
| LIT-050 v2 | Mean-Field-Type Game Theory with Rosenblatt Noise | Tembine et al. (2025), ARXIV-2506.08025. The paper’s control and game results use linear state feedback, and they depend on the Rosenblatt noise only through its covariance, which is exactly fBM’s with the same H. They are therefore identical to the fBM results. The ergodic LQ gain (Thm 4), K̂ = −[b₁ + √(b₁² + 4H(1−H)b₂²q/r)]/(2b₂(1−H)), is correct and reduces to the Brownian LQR gain at H = ½. But the paper’s headline “suboptimality of noise approximation” (§VI-A, repeated for the variance-aware control, zero-sum, non-zero-sum and MFTG settings) holds only against surrogates with a different covariance; against fBM with the same H it is false. The ML claim that Rosenblatt “super-diffusion transformers” “significantly enhance the performance of generative machine intelligence models” (§XIV-C) has no model, training, dataset or experiment behind it anywhere in the paper. | Rejected — read in full 2026-09-25 (NOTE-068); not worth a reader’s time. The control-theoretic results are earlier papers’ (its refs [43]–[46]) restated. Its central new claim, that Gaussian and fBM surrogates give suboptimal control, is false for fBM with matching H, since the costs depend only on covariance. Its empirical sections are unsourced vignettes: numbers without references, “Rosenblatt shape” fits without any fitting procedure, and data from the first author’s own startups. Its ML claim is an assertion with no model or experiment. A reader wanting Rosenblatt-noise LQ control should go to Čoupek–Duncan–Maslowski–Pasik-Duncan (CDC 2018, ref [43]) and Čoupek–Duncan–Pasik-Duncan (SPA 2022, ref [27]). |
| LIT-051 v2 | Lecture Notes on Control System Theory and Design | Başar et al. (2020), ARXIV-2007.01367. A conventional first-year graduate course in linear state-space control. It covers modelling and linearisation, LTI/LTV solutions, Lyapunov stability, controllability and observability with Kalman/Hautus tests and minimal realisations, then pole placement and observers, integral control, sensitivity, and finally HJB/LQR and a heuristic minimum principle. Its most useful non-standard content is the Pendubot thread (Chs 1, 9, 10): an observer-based design from one sensor is fragile (the compensator has an unstable pole at s ≈ 46.4), while full-state LQR has |S(jω)| ≤ 1, infinite gain margin and ±60° phase margin. Every worked example I recomputed is correct. | Active — read in full 2026-09-25 (NOTE-062); a sound, free, compact state-space control course, worth reading as background for LQR, Lyapunov and HJB when a reader needs one place for them. It is not a source for anything current, and the preface’s promise of a reinforcement-learning bridge is not delivered in the text. |
| LIT-352 v2 | A numerical algorithm for block-diagonal decomposition of matrix *-algebras with application to semidefinite programming | Murota et al. (2010), DOI-10.1007/s13160-010-0006-9. Given real symmetric A₁…A_m, the method finds an orthogonal P that block-diagonalises them all as simultaneously and finely as possible. That is the decomposition of the matrix *-algebra 𝒯 they generate into simple components (Algorithm 4.1) and then irreducible components (§4.2), with no group or algebra supplied in advance. The simple components are the connected components of the graph “Q_iᵀA_pQ_{i′} ≠ O” between the eigenspaces of one random combination A(r) = Σ r_pA_p. This is correct with probability 1 when span{I, A₁…A_m} = 𝒯 ∩ Sⁿ (Props. 3.2–3.4, 4.2). The structure theorem it relies on, Theorem 3.1(C) “if 𝒯 is irreducible then 𝒯 = Mₙ”, is false over ℝ as stated. The companion paper (Maehara & Murota 2010) handles the complex and quaternion types. | Active — read in full 2026-09-29 (NOTE-276); worth reading as the clearest short account of numerical block-diagonalisation of a *-algebra from generators alone, via eigenspaces of a random element. For the general real case, i.e. irreducible components of complex or quaternionic type, the companion Maehara & Murota (JJIAM 27:263–293, 2010) is needed, and is not in the record. For the map’s use, both should be cited. |
| LIT-868 | A Generalized Information-Theoretic Framework for the Emergence of Hierarchical Abstractions in Resource-Limited Systems | Larsson, Maity and Tsiotras (2022), Entropy 24(6):809. Treats a pruning of a fixed quadtree as a deterministic encoder of the grid and maximises Σβ_i I(T;Y_i) − Σγ_j I(T;Z_j) − αI(T;X) over such prunings. Every term splits over interior nodes (p(t)·JS of the children’s conditionals; p(t)H of the split), so a bottom-up recursion (G-tree search) returns the optimal tree with fewest leaves in linear time. Recovers the IB and IB-with-side-information trees as special cases and proves the latter is always a pruning of the former. | Active — read 2026-10-09 (NOTE-676); worth reading as an exact solution of a structured information-bottleneck problem: when the encoder must be a pruning of a fixed tree (here the dyadic quadtree of a grid), every information term splits over the interior nodes, a node’s share of I(T;Y) being p(t) times the Jensen–Shannon divergence of its children’s p(y|·) and its share of I(T;X) being p(t)H(Π). A bottom-up recursion, G(t) = max{ΔJ(t) + Σ G(children), 0}, then returns the optimal tree with the fewest leaves for any weighted sum of relevance, irrelevance and compression terms, in time linear in the grid. A greedy top-down search can miss all the relevant information, because a node whose children predict Y alike gains nothing however much its grandchildren differ. Adding an irrelevance penalty can only prune the plain IB tree. The hierarchy is given, not found: what “emerges” is which coarse-graining of a fixed quadtree to keep. |
| LIT-1080 | Selection of Views to Materialize in a Data Warehouse | Gupta and Mumick (2005), IEEE TKDE. The journal paper merges Gupta’s 1997 space-budget results and the 1999 maintenance-budget results into one article; it adds proofs, not new problems or new guarantees. Theorem 8 (the conference Theorem 1: inverted-tree greedy on OR view graphs, at most 2S of maintenance, at least 1 − 1/e of an optimum with the same maintenance, assuming no inverted-tree piece of the optimum exceeds S) and Theorem 10 (A* is exact on AND-OR graphs) are now proved, while Theorem 9 (the assumption-free half-density bound) is referred to Gupta’s thesis. The maintenance-budget guarantee stays confined to OR view graphs, the greedy stays exponential in the worst case, and the two constraints are never combined. The only place upkeep is traded against query cost is the 1997 formulation carried over, query cost plus maintenance cost minimized under a space budget, with a guarantee only for AND view graphs in which every view is queried more often than it is updated; build cost and staleness are not modelled anywhere. | Active — read in full 2026-10-15 from the first author’s manuscript of the journal paper, linked from Gupta’s publication list (www3.cs.stonybrook.edu/~hgupta/ps/sel-views-tkde.pdf, 41 single-column pages, read by OCR; not compared with IEEE’s typeset pp. 24–43). Worth reading as the consolidated, proved account of Gupta’s 1997 space-budget results (LIT-1091) and Gupta and Mumick’s 1999 maintenance-budget results (LIT-1092): it is the journal version of both papers, not of the 1999 paper alone, and it adds proofs, not new problems or guarantees. The inverted-tree greedy’s 1 − 1/e guarantee for OR view graphs under a maintenance budget (now Theorem 8, still bicriteria at up to 2S and still assuming no tree-piece of the optimum exceeds S) and the exactness of A* on AND-OR graphs (Theorem 10) are now proved; the assumption-free half-density bound (Theorem 9) is referred to Gupta’s thesis; the guarantee is still for OR graphs only and the greedy still exponential in the worst case, data cubes included. For QUESTION-114 it changes nothing: the article holds two separate models, upkeep in the objective under a space budget (guaranteed only for AND view graphs in which every view is queried more often than updated, a lemma it now says fails for OR graphs) and upkeep as a budget with query cost alone in the objective, never both constraints together, and no build cost or staleness. LIT-1095 remains the closest to a joint model. |
| LIT-1083 | An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server | Chaudhuri and Narasayya (1997), VLDB ‘97. The AutoAdmin tool picks at most k indexes (single- or two-column, clustered or not) for a given workload of SQL statements, minimising the unweighted sum of the optimizer’s estimated costs of those statements, with hypothetical (“what-if”) indexes made visible to the optimizer by loading their statistics into the catalog. Its contribution is search efficiency: candidates are restricted to indexes in some single query’s best configuration, enumeration is Greedy(m, k) (an exhaustive seed of m indexes, then greedy additions), costs of most configurations are derived from a few “atomic” ones, and two-column indexes are generated only from winning single columns. On five TPC-D workloads this cut running time to 10–24% of a baseline, with estimated-cost quality 0–7% worse, and Greedy(2, 4) matched the exhaustive optimum on four of five workloads and was within 1% on the fifth. The cost model has no build cost, no storage term and no frequency weights, the budget is a count of indexes, the workload is fixed, there is no guarantee for the greedy step, and quality is never measured by executing anything. | Active — read in full 2026-10-15 from the VLDB Endowment’s proceedings PDF (www.vldb.org/conf/1997/P146.PDF, pp. 146–155, a scan with an OCR layer; tables and figures read from page images), which refuses plain requests from this environment (HTTP 403) and was served when the request carried a browser User-Agent. Worth reading as the founding paper of optimizer-driven (“what-if”) index selection in practice: at most k indexes chosen for a fixed workload of SQL statements to minimise the unweighted sum of the optimizer’s estimated costs, made affordable by per-query candidate selection, Greedy(m, k) enumeration with an exhaustive seed, derived costs from atomic configurations, and two-column indexes grown from single-column winners (4–10 times faster than a baseline, 0–7% worse by estimated cost, on five TPC-D workloads). For QUESTION-114 it prices organizing ahead no differently from Finkelstein et al. (LIT-1084), and in fewer terms: upkeep through the workload’s update statements, but no build cost, no storage term, no frequency weights and no changing workload, so “paid once” and staleness stay unpriced; what it adds is that deciding the arrangement has its own cost, and evidence (not a bound) that greedy choice works when index interactions are few and local. For CLAIM-310 it is consistent with the dependence on the query mix by construction and says nothing about what stands out within a bin; its heuristics (consider only sortings best for some search, choose the first carefully and add the rest greedily) carry over to a builder’s bins only by analogy. |
| LIT-1084 | Physical database design for relational databases | Finkelstein, Schkolnick and Tiberio (1988), ACM TODS 13(1). DBDSGN chooses, for each table, one clustered (ordering) index and a set of nonclustered indices to minimise a frequency-weighted sum of per-statement costs (access, tuple update, index maintenance) plus a weighted storage term, under an optional page limit, taking every cost from the System R optimizer’s own estimates rather than an external model. Statement costs for any configuration are computed exactly from “atomic” configurations with at most one index per table (Propositions 1 and 2), so the optimizer is consulted a linear rather than exponential number of times per table; with no elimination heuristics and a full search the tool finds the optimum, but only with respect to the optimizer’s estimates. The paper gives one worked example and no measurement of actual execution, and its claims that the heuristics usually find the best solutions are not backed by reported data. The model is steady-state over a period: it has no term for the one-time cost of building an index or sorting a table, so it prices upkeep against retrieval, not a one-off sort against later retrievals. | Active — read in full 2026-10-15 from the publisher’s typeset PDF (ACM TODS 13(1), pp. 91–128), which ACM serves free at dl.acm.org/doi/pdf/10.1145/42201.42205 (bronze) but which refused requests from this environment (HTTP 403; the Internet Archive capture could not be fetched), so the copy was the same ACM PDF as posted by the University of Crete course CS-460 (www.csd.uoc.gr/~hy460/pdf/p91-finkelstein.pdf). Worth reading as the classic statement of index selection as a workload-weighted cost model: one clustered order per table (“records can be ordered only one way”) plus secondary indices, chosen to minimise the weighted sum of access, tuple-update and index-maintenance costs plus weighted storage under a page limit, with every cost taken from the optimizer’s own estimates; exact over atomic configurations and optimal only relative to those estimates, with heuristic pruning and no measurement of actual execution. For QUESTION-114 it supplies the joint model for standing arrangements (bins, filed items), but it has no term for the one-time cost of sorting or building an index and does not cover precomputed answers (speed bugs, reused inferences); for CLAIM-310 it is an instance of “one arrangement” and of dependence on the query mix, has no analogue of a bin budget k, and nothing corresponding to pop-out within a bin. |
| LIT-1091 | Selection of views to materialize in a data warehouse | Gupta (1997), ICDT ‘97. Gupta states view selection on general AND-OR view graphs as minimizing frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget. He proves greedy guarantees of 1 − 1/e (about 63%) of the optimal benefit, with the budget overrun by one view or up to double, but almost all of them assume no updates. Maintenance cost enters exactly one theorem: AND view graphs (each view has one way of being computed) in which every view is queried more often than it is updated. For OR view graphs, which include Harinarayan, Rajaraman and Ullman’s data cube, the paper sets update costs aside outright, so it does not add upkeep to that problem. Maintenance is an abstract per-update charge for keeping a view consistent. Nothing prices building a view, tolerated staleness or deferred refresh, and there are no experiments. | Active — read in full 2026-10-15 from the author’s PostScript copy on the Stanford InfoLab papers server (infolab.stanford.edu/pub/papers/SelectionViews.ps, 15 pp., dated March 1997, linked from the warehousing project’s publication page; Unpaywall and OpenAlex report the DOI closed). Worth reading as the general statement of view selection: AND-OR view graphs with query and update frequencies, and an objective of frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget, with greedy guarantees of 1 − 1/e of the optimal benefit when space may overrun. For QUESTION-114 it gives the joint objective in form: reuse against per-update upkeep under capacity. It charges no build cost, leaves the maintenance cost abstract, and models only keeping views consistent, not tolerating or acting on stale ones. Its guarantees with maintenance cost hold only for AND view graphs in which every view is queried more often than it is updated. For the data cube of LIT-1094 it assumes no updates, so it does not add upkeep to that problem. That came in Gupta and Mumick’s maintenance-time-constrained follow-up (ICDT 1999), read afterwards as LIT-1092. |
| LIT-1092 | Selection of Views to Materialize Under a Maintenance Cost Constraint | Gupta and Mumick (1999), ICDT ‘99. Gupta and Mumick choose views to materialize so as to minimize frequency-weighted query cost subject to a cap S on total maintenance time, the sum over chosen views of update frequency times a per-update maintenance cost that depends on which other views are stored. Because storing one view can make another cheaper to maintain, benefit per unit of maintenance is not monotone and the single-view greedy of earlier work can be arbitrarily bad. For OR view graphs (each view computed from one other, as in data cubes) a greedy that adds whole “inverted tree sets” gets at least 1 − 1/e (63%) of the benefit of an optimal solution that may use as much maintenance as the greedy did, the greedy using up to 2S, assuming no inverted-tree piece of the optimum alone exceeds S (Theorem 1, unproved here); without that assumption it gets half the optimum’s benefit per unit of maintenance (Theorem 2). Each greedy stage enumerates exponentially many sets in general; for general AND-OR graphs there is only an exact A* search with exponential worst case. Upkeep is a budget, not a term traded against query savings; build cost, storage and staleness are not modelled, and the experiments are on random graphs of 10 to 25 nodes. | Active — read in full 2026-10-15 from the authors’ PostScript copy on Stanford InfoLab’s papers server (infolab.stanford.edu/pub/papers/update.ps, 18 pages, dated 8 October 1998, the ICDT ‘99 camera-ready, not the 2005 TKDE journal version; not compared with Springer’s typeset pages). Worth reading as the first view-selection result that budgets maintenance time instead of space, and for its demonstration that upkeep is not additive: storing one view can make others cheaper to maintain, so benefit per unit of maintenance is not monotone and single-view greedy can be arbitrarily bad. For QUESTION-114 it shows upkeep priced as a budget, U(M) = Σ update frequency × per-update maintenance cost given the other stored views, with query cost the only objective; build cost, storage and staleness are not modelled (every view is refreshed in a nightly batch). Its guarantee answers the open problem of LIT-1091 only for OR view graphs: 1 − 1/e of an optimum’s benefit while using up to twice the budget, under an assumption on the optimum, or half the optimum’s benefit per unit of maintenance without it, with the theorems stated but not proved and a greedy whose stages are exponential in general (including on data cubes). General AND-OR graphs get only an exact A* search. It does not close the question, and comes no closer to a joint cost model than LIT-1095. |
| LIT-1094 | Implementing data cubes efficiently | Harinarayan, Rajaraman and Ullman (1996), SIGMOD ‘96. Treats a data cube’s group-by queries as a lattice in which a query can be answered from any stored ancestor, prices a query at the number of rows of the smallest materialized ancestor, and chooses which views to precompute. Choosing k views to maximize the total reduction in query cost (the “benefit”) is NP-complete; a greedy rule that adds the view of largest marginal benefit gets at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimal benefit, a bound that is tight, holds unchanged with query-frequency weights, and weakens to 0.63 − f under a space budget when no view takes more than a fraction f of it. The cost of building views is represented only by their size, maintenance and updates are not modelled, the data are static, and the bound is on benefit, not on query cost. On TPC-D data the greedy order reaches nearly the minimum total query time with five views and barely more space than the base view. | Active — read in full 2026-10-15 from the authors’ 25-page version on Stanford InfoLab’s papers server (infolab.stanford.edu/pub/papers/cube.ps, TeX run of 8 January 1996), not the SIGMOD typesetting, which the ACM Digital Library refused (403); the two were not compared. Worth reading as the standard source on choosing which precomputed answers to store when each query is answered from its cheapest stored ancestor: the lattice of group-by views, the linear cost model (rows of the ancestor scanned), NP-completeness, and a greedy rule whose total benefit, the saving against storing the base view alone, is at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimum for a budget of k views, tight, unchanged with fixed query frequencies, and only 0.63 − f under a space budget when no view exceeds a fraction f of it. For QUESTION-114 and QUESTION-095 it shows the precomputed-answer term the four earlier readings lacked, with a stored answer’s value counted over every query it serves and marginal on what is already stored (sharpening CLAIM-303’s break-even); it does not price build cost (space is a proxy), upkeep or staleness (the data are static and derived answers exact), timing or deadlines, uncertain workloads, or the medium of retrieval, so it is a model of the speed bugs only in naming the category, an analogy with one usable term for filed arguments, silent on the bias of reused inferences, and not about LEGO bins. |
| LIT-1101 | Effective Page Refresh Policies for Web Crawlers | Cho and Garcia-Molina (2003), ACM TODS 2003. Unavailable: a lawful copy exists but could not be fetched. | Unavailable — filed 2026-10-15, not read. Looked for a lawful full text of the journal version (ACM TODS 28(4), 2003) on 2026-10-15 and found one that could not be fetched. The authors’ own copy is listed at oak.cs.ucla.edu/~cho/papers/cho-tods03.pdf (a web search returns it with the title “Effective Page Refresh Policies For Web Crawlers”), but that server did not answer from this environment: nine requests over about seven minutes each returned 503 with an upstream connection timeout, and WebFetch got the same; the author’s index page there, and the old Stanford address infolab.stanford.edu/~cho/ (which redirects to it), behaved the same, and web.cs.ucla.edu/~cho/papers/cho-tods03.pdf is 404. The ACM Digital Library returned 403. Unpaywall and Semantic Scholar report it closed; OpenAlex reports it closed and lists two CiteSeerX records (10.1.1.3.7723, 10.1.1.89.8050), which could not be reached (connection reset, then a redirect to the Internet Archive, which is unreachable from here). ResearchGate’s page returned 403, and who uploaded its copy is unknown. Stanford’s InfoLab technical-report server (ilpubs.stanford.edu:8090) timed out. The University of Crete course page holds slides about the paper, not the paper. What is lawfully available is the other version: the SIGMOD 2000 conference paper (LIT-1119, read), and the authors’ October 1999 Stanford technical report of it on a KTH course page, which lacks what the journal adds (by its abstract and secondary accounts, among other things, refresh weighted by page importance). Found but could not be fetched. |
| LIT-1105 | Balancing Performance and Data Freshness in Web Database Servers | Labrinidis and Roussopoulos (2003), VLDB 2003. The paper poses Online View Selection for a web server whose database takes updates while serving requests: choose, as the workload runs, which page fragments (WebViews) to keep stored and refreshed on every update and which to cache and invalidate, so as to minimize mean response time while the fraction of fresh fragments served (QoD) stays above a threshold θ. Its algorithm, OVIS(θ), estimates per fragment the response-time and QoD change of switching, and periodically switches up to MAX_CHANGE fragments greedily, spending a QoD surplus on speed or buying back a deficit; it materializes everything when it detects backlog. Nothing is proved: optimality of the greedy step is asserted, and the evidence is one synthetic simulation with fixed costs, in which OVIS kept QoD near θ, answered faster than caching alone, and recovered from overload. Upkeep and query savings share one cost, but staleness is a constraint set by the user, not a priced term, and build cost, switching cost and storage are absent. | Active — read in full 2026-10-15 (NOTE-911) from the VLDB Endowment’s copy of the 2003 conference paper (www.vldb.org/conf/2003/papers/S13P01.pdf, 12 pp.; Crossref pages 393–404), whose bitmap fonts made OCR necessary; the 2004 VLDB Journal version was not read. Worth reading as the first online view-selection algorithm that trades response time against a measured freshness: OVIS(θ) periodically moves up to a fixed number of page fragments between cached-and-invalidated and stored-and-refreshed, greedily, to keep the share of fresh fragments served above θ at the least response time, and materializes everything when it detects backlog. For QUESTION-114 it is not the joint model: query savings and upkeep share one cost and staleness is measured, but staleness is a threshold, not a price, switching and storage are free, the greedy’s optimality is asserted without proof, and the evidence is one synthetic simulation with fixed costs; set beside Bruno and Chaudhuri (THEORY-332), which has build cost and no staleness, neither contains the other. For CLAIM-303 it adds a third option, keep the result and invalidate it on change, and measures staleness as a share of uses, not a cost. |
| LIT-1109 | Adaptive Precision Setting for Cached Approximate Values | Olston et al. (2001), SIGMOD 2001. Olston, Loo and Widom set the width of each cached interval adaptively to minimize total refresh traffic. A narrow interval is escaped often (value-initiated refreshes, cost C_vr); a wide one is too imprecise for queries more often (query-initiated refreshes, cost C_qr). Under a model in which these probabilities go as 1/W² and W, the expected cost rate is least where ρ·P_vr = P_qr, ρ = 2C_vr/C_qr, and a rule that widens on value-initiated and narrows on query-initiated refreshes, with probabilities set by ρ, reached within 1% to 5% of the best fixed width in simulation. That the rule converges is argued, not proved. With exact copies required it matched an adaptive exact-caching algorithm, and where imprecision was allowed it beat it. Staleness is priced as refresh traffic only: there is no build cost, no cost of a wrong answer, and the interval is never wrong. | Active — read in full 2026-10-15 from the copy in the University of Pennsylvania’s repository (ScholarlyCommons cis_papers 1351, repository.upenn.edu/server/api/core/bitstreams/92340f91-673c-435e-9b4e-b24072d4d96b/content), the camera-ready text with printed pages 355–366. Worth reading as the one model the record holds in which staleness and upkeep are traded in a single objective: a cached interval of width W is escaped (a pushed refresh, cost C_vr) more often when narrow and is too loose for queries (an exact fetch, cost C_qr) more often when wide, and under the paper’s model the least expected cost is where ρ·P_vr = P_qr with ρ = 2C_vr/C_qr (THEORY-386); a rule that widens on one kind of refresh and narrows on the other came within 1–5% of the best fixed width in simulation and, restricted to exact copies, matched an adaptive cache-or-not algorithm (THEORY-377). For QUESTION-114 it prices staleness as refresh traffic, with no build cost, no stored answers and no cost of a wrong answer, since the source guarantees validity. For CLAIM-303 it gives upkeep and per-use verification a common dial, but only where a source sees every change; for CLAIM-308 its exact-caching case is a forecast-free counting rule justified in expectation, not in the worst case, and once staleness is admitted the two-state choice becomes a continuum with an interior optimum. |
| LIT-1117 | Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data | Olston and Widom (2000), VLDB 2000. Olston and Widom propose TRAPP: caches hold, for each numeric value, an interval its source guarantees to contain the current value, the source pushing a refresh whenever the value leaves it. A query carries a precision constraint R, and the system chooses which values to fetch exactly so that the answer interval is at most R wide whatever the true values, at least total refresh cost. For SUM (and AVG without a predicate) that choice is a 0/1 knapsack problem, NP-complete in general and polynomial with equal costs; COUNT and MIN have simple rules. Staleness becomes bounded imprecision, never error, and the cost of the source-side upkeep that guarantees this, and of setting the bound widths, is outside the optimization. The one experiment is 90 stock prices with random costs. | Active — read in full 2026-10-15 from the VLDB Endowment’s open copy of the proceedings paper (www.vldb.org/conf/2000/P144.pdf, pp. 144–155; the server needs a browser User-Agent). Worth reading as the source of the idea that a cached value can be held as an interval its source guarantees, so that staleness becomes a bounded, stated imprecision instead of an unknown error, and a query buys precision down by paying for exact reads; for SUM, choosing the cheapest reads that meet a width R is a 0/1 knapsack problem (THEORY-364). For QUESTION-114 it gives staleness a unit (bound width against a query’s tolerance) and prices only the query side: the source’s upkeep that makes the bound a guarantee, and the choice of bound widths, are assumed and uncosted, imprecision is a hard constraint rather than a loss, and a stale read can never be wrong. For CLAIM-303 it sharpens “verification” into a per-use decision against a stated tolerance, but rests on a source that watches every copy, which a filed argument lacks, so it does not price the cost of reusing an obsolete conclusion; it does not bear on CLAIM-308’s rent-or-buy argument. LIT-1109 prices the upkeep side. |
| LIT-1118 | WebView Materialization | Labrinidis and Roussopoulos (2000), SIGMOD 2000. For a page built from database queries, the paper compares three ways to serve it on a server with online updates: compute it on each request (virt), store the query result in the DBMS and refresh it on every update (matdb), or store the finished page as a file at the web server and rewrite it on every update (matweb). It gives a cost model summing access and update costs by their frequencies and states the selection problem (choose a policy per page to minimize mean response time, no space limit, no staleness allowed), but gives no algorithm for it. On one Apache/Informix testbed with cheap indexed queries, matweb answered 10 to 230 times faster than the other two at all loads tried, and matdb was slower than virt whenever there were updates, because reading the stored result cost about as much as recomputing it. Staleness is defined as the delay from update to reply, sketched, and never measured; build cost and storage are outside the model. | Active — read in full 2026-10-15 (NOTE-908) from the authors’ camera-ready copy on the University of Maryland Opsis project page (www.cs.umd.edu/projects/opsis/papers/2000/webviews.pdf, 12 pp., dated 1 March 2000); the ACM Digital Library copy returned 403. Worth reading as the first cost model for choosing, per database-generated web page, between computing it on request, storing the query result in the DBMS, and storing the finished page at the web server, with every stored copy refreshed on each update; on one Apache/Informix testbed the page stored at the web server answered 10 to 230 times faster, and the result stored in the DBMS lost to recomputation whenever there were updates, because reading it cost about as much as rebuilding it. For QUESTION-114 it prices access and upkeep by frequency and adds where the copy is stored, but forbids staleness, has no build cost or storage term, and states the selection problem without an algorithm; for CLAIM-303 it shows filing failing through access cost alone, and upkeep slowing the unfiled reads that share its resource (by 236% in its model check). |
| LIT-1119 | Synchronizing a Database to Improve Freshness | Cho and Garcia-Molina (2000), SIGMOD 2000. For a local copy of N items, each changing as an independent Poisson process with a known rate and refreshed at fixed intervals under a fixed total refresh rate, refreshing every item equally keeps the copy fresher and younger on average than refreshing in proportion to change rate, under any distribution of rates (proved in the technical report by convexity). The freshness-optimal allocation is neither: it rises and then falls with change rate, and gives no refresh at all to items that change too fast for the budget, while the age-optimal allocation rises slowly with change rate. On estimates from 270 web sites, proportional, uniform and optimal refresh give freshness 0.12, 0.57 and 0.62. Every item matters equally, staleness is a time average with no access or query model, the refresh budget is fixed rather than priced, and refresh, change and its detection are free of any other cost. | Active — read in full 2026-10-15 from the conference version as published, the PDF of SIGMOD 2000 pp. 117–128 served by ACM SIGMOD’s SIGMOD Record site for the June 2000 proceedings issue (sigmodrecord.org/publications/sigmodRecord/0006/pdfs/Synchronizing%20a%20Database%20to%20Improve%20Freshness.pdf), with the proofs it defers checked in the authors’ 1999 Stanford technical report as hosted on a KTH course page. Worth reading as the standard definition of a copy’s freshness and age under Poisson change, and for the result that, under a fixed refresh budget, refreshing every item equally beats refreshing in proportion to change rate for any distribution of rates, while the freshness-optimal allocation gives nothing to items that change too fast to follow. For QUESTION-114 it is the first reading that prices staleness instead of forbidding it, but as an objective under a fixed budget, with no reads, no query savings and no build cost, so it supplies the staleness term and not the joint model; for CLAIM-303 it models the re-checking term per unit time and by rate of change, not per use, and does not price the cost of a stale use. |
| LIT-1155 v2 | The geometry of graphs and some of its algorithmic applications | Linial, London & Rabinovich (1995), Combinatorica 15(2): 215–245. Every n-point metric embeds in O(log n)-dimensional Euclidean space with distortion O(log n) (Bourgain’s theorem as Theorem 3.2(1) states it). The paper reproves the distortion by a randomized map to distances from O(log² n) random sets, takes the dimension from Johnson–Lindenstrauss, and computes the least Euclidean distortion of any finite metric by semidefinite programming. Constant-degree expanders need distortion Ω(log n) in ℓ_p, 1 ≤ p ≤ 2, of any dimension (Proposition 4.2), so the bound is tight. The max-flow/min-cut gap for k commodities is O(log k), with a deterministic algorithm (Theorem 4.1). | Active — read 2026-10-16 (NOTE-928) in full; worth reading as the place where Bourgain’s O(log n) embedding of finite metrics into Euclidean space is restated, reproved by distances to random sets of every scale, and shown tight: constant-degree expanders need distortion Ω(log n) in ℓ_p, 1 ≤ p ≤ 2, of any dimension, because their gap between multicommodity flow and cut is Ω(log n). The same embeddings bound that gap by O(log k) for k commodities. Read it knowing that the O(log n) dimension comes from Johnson–Lindenstrauss, not from the construction, which uses O(log² n) coordinates; that the lower bound rests on Leighton and Rao’s gap, cited; that constants are unspecified; and that it says nothing about trees in ℓ₂, for which Sala et al. cite it. Filed as THEORY-394. |
| LIT-1212 v2 | Multiple-gradient descent algorithm (MGDA) for multiobjective optimization | Désidéri (2012; first as an INRIA report, 2009). A point is Pareto-stationary when some convex combination of the criteria’s gradients is zero, which every Pareto-optimal point is; when a point is not, minus the minimum-norm element of the gradients’ convex hull is a descent direction common to all smooth criteria, and steepest descent along it (MGDA) has a subsequence converging to a Pareto-stationary point when the criteria are positive and coercive. | Active — read 2026-10-29 (NOTE-1401) in full, from the Comptes Rendus Mathématique’s own open copy of the 2012 note; worth reading as the short published source for Pareto-stationarity and for the minimum-norm point of the gradients’ convex hull as a common descent direction, the constructive half of CLAIM-366’s convex-hull test. Read it knowing that it does not state the converse (zero in the hull excludes common strict descent), that its convergence theorem’s proof is a sketch, and that the direction, unlike its existence, depends on how the gradients are scaled, which the author leaves open. |
| LIT-1217 v2 | Practical Byzantine Fault Tolerance | Castro & Liskov (1999), OSDI ‘99, pp. 173–186. A state-machine replication protocol that keeps safety with at most f of 3f + 1 replicas Byzantine-faulty and no timing assumption, using weak synchrony only for liveness, with MACs in place of signatures in the normal case. A Byzantine-fault-tolerant NFS on four replicas ran the Andrew benchmark 3% slower than Digital Unix’s NFS, measured without faults and with view changes not yet implemented. | Active — read 2026-10-29 (NOTE-1356) in full, from the copy MIT’s 6.824 course hosts (pdos.csail.mit.edu), the proceedings text of pp. 173–186; worth reading as the paper that made Byzantine-fault-tolerant state-machine replication practical: safety with at most f of 3f + 1 replicas faulty and no timing assumption, liveness under weak synchrony, a faulty primary replaced by rotation rather than by voting anyone out. Read it knowing that correct behaviour is defined as following the protocol, so the service’s own specification is taken as given; that its fault bound needs independent failures the paper says must be engineered; and that its measurements are of the normal case on four replicas, with view changes not implemented in the measured library. |
| LIT-1365 v2 | National Incident Management System, Third Edition | FEMA (2017). The national doctrine for incident management in the United States: the Incident Command System’s modular organization, Unified Command (in which participating agencies keep their own authority and accountability), and the Safety Officer’s authority to stop or alter activities that are immediately dangerous. | Active — skimmed 2026-10-22 (NOTE-1072) from FEMA’s PDF (a U.S. government work): the Introduction and the Command and Coordination component read in full, with the command-position tables of Appendix A; Resource Management skimmed; Communications and most appendices not read. Worth holding as the doctrine the record’s incident cases are measured against: Unified Command shares the command function among agencies that keep their own authority, transfer of command is formalized with a briefing, and the Safety Officer may alter, suspend or terminate immediately dangerous activities. It also keeps one command function, one action plan and unity of command, which limits A24’s reading that coordination needs no single controller. Doctrine, not evidence of practice. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1371 v2 | Aircraft Accident Report: United Airlines, Inc., McDonnell-Douglas DC-8-61, N8082U, Portland, Oregon, December 28, 1978 | NTSB (1979). United 173 ran out of fuel while its crew worked a landing-gear problem near Portland, and crashed, killing ten. The probable cause was the captain’s failure to monitor and respond to the fuel state and to the crew’s advisories; a contributing factor was the other crew members’ failure to grasp or press the criticality of the fuel state. The Board recommended that crews be indoctrinated in “flightdeck resource management”, with participative management for captains and assertiveness training for the rest of the crew. | Active — read 2026-10-22 (NOTE-1086) from the FAA-hosted scan of NTSB-AAR-79-7 (a U.S. government work; the analysis and findings pages read from images where the OCR fails; the CVR transcript skimmed). Worth holding as the founding document of the CRM case: the crew had the fuel quantity, no one was assigned to watch it against time, the others’ concerns stayed comments, and the Board’s recommendation X-79-17 asked for “participative management for captains and assertiveness training for other cockpit crewmembers”, a reform of how command takes input that leaves command in place. It does not find that the other crew members knew the fuel was running out. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1374 v2 | Post-Incident Analysis: Independent Review of the Brookhollow Apartment Fire | Jensen Hughes (2024). The independent review, commissioned by Sedgwick County and the City of Wichita, of the emergency response to the Brookhollow Apartments fire of 13 October 2023, in which a resident, Paoly Bedeski, died and a partial collapse of the exterior stair roof on two fire crews brought a mayday. It found “no single point of failure” but systemic shortcomings across dispatch and the fire department that “contributed to an unorganized rescue effort”, most of them departures from the agencies’ own procedures, without concluding that they changed the outcome. | Active — read in full 2026-10-22 (NOTE-1073) from the report as posted by Sedgwick County, which commissioned it. Worth holding as the record’s best documented instance of CLAIM-422’s procedure–capacity gap: the agencies’ written procedures were judged thorough and up to date, and the failures were departures from them (a CAD step dispatchers on several shifts could not recall, a TAC-monitoring rule set aside by informal agreement, a mayday policy not followed, search not resumed for over eleven minutes after a mayday under control within minutes). It does not support “four firefighters caught”; it names two crews and reports no firefighter injured. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1378 v2 | NASA: Better Mechanisms Needed for Sharing Lessons Learned | GAO (2002). Found that NASA’s lessons-learned system was little used by its program and project managers, and that the agency had no assurance that lessons from earlier failures were being applied. | Active — read in full 2026-10-22 (NOTE-1088) from the GAO’s PDF on govinfo.gov (a U.S. government work). Worth holding as a clean instance of procedure without capacity at NASA: agency rules required managers to review and apply lessons, a 2001 census survey found they mostly did not, and NASA measured how often its lessons database was searched but not whether any lesson was applied. It is about the 1999 Mars failures and a 1995 database, not about Challenger or the Shuttle, so it is not evidence that the post-Challenger corrections decayed. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1386 v2 | The Evolution of Crew Resource Management Training in Commercial Aviation | Helmreich, Merritt and Wilhelm (1999). Traces CRM through five generations, from training aimed at captains’ management style and juniors’ assertiveness after accidents such as United 173 to error management: avoiding, trapping and mitigating error. Reports that accident rates cannot validate CRM, that acceptance of its concepts decays over time even with recurrent training, and that it exported poorly to high power-distance cultures. | Active — read in full 2026-10-22 (NOTE-1087) from the authors’ manuscript (UT Austin Human Factors Research Project 235), hosted by the FAA, which funded the work. Worth holding for two reported findings rather than for what the record cited it for: acceptance of CRM concepts slips in the years after training even with recurrent training, and CRM designed in the U.S. fits poorly in high power-distance cultures; and for its statement that accident rates cannot validate CRM. It does not argue that CRM keeps command while opening challenge; that phrasing is the exchange’s. A review with no new data. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1393 v2 | Report of the Presidential Commission on the Space Shuttle Challenger Accident | Rogers Commission (1986). The presidential commission’s report on the loss of Challenger on 28 January 1986. It traces the O-ring failure to a history of erosion that had been accepted flight by flight, recounts Morton Thiokol’s reversal of its engineers’ recommendation against launch on 27 January “at the urging of Marshall”, and finds the safety, reliability and quality-assurance program ineffective, understaffed and absent from the decision (chapter VII, “The Silent Safety Program”). | Active — skimmed 2026-10-22 (NOTE-1090) from the NASA History Office’s HTML edition of volume 1 (a U.S. government work): chapters V–VIII and the Recommendations in full, chapters III, IV and IX in part, volumes 2–5 not read. Worth holding as the primary source for the Challenger half of THEORY-140: it documents, in 1986, the accepted-erosion trajectory, a launch constraint waived six times without Levels I and II knowing, the deliberate decision not to escalate Thiokol’s objection, a problem record marked “closed” with no correction behind it, and a safety organization subordinate to the offices it checked. Registered from the owner’s exchange of 2026-10-22, “Graph Learning Applications”. |
| LIT-1613 v2 | Engineering a Safer World: Systems Thinking Applied to Safety | Leveson (2011). STAMP treats accidents as failures to enforce safety constraints in a hierarchical control structure, including unsafe interactions among components that each behave as designed, rather than as chains of component failures; STPA is the hazard analysis built on it. | Unfetched — searched 2026-10-29 for a lawful full text; the book is open access and copies exist, but this client could not fetch any, so it is not read and no NOTE is filed. OpenAlex lists it as open access at MIT Press Direct (doi:10.7551/mitpress/8179.001.0001) and in the Directory of Open Access Books (handle 20.500.12854/78510); catalogue records give the OAPEN Library file https://library.oapen.org/bitstream/handle/20.500.12657/26043/1004042.pdf. On 2026-10-29 MIT Press Direct returned a Cloudflare 403 challenge to curl; library.oapen.org returned 403 with an anti-bot page (“Making sure you’re not a bot!”) to curl and timed out to WebFetch, and the DOAB and OAPEN APIs refused the client’s address. The author’s site copy at sunnyday.mit.edu/safer-world.pdf returned 503 behind the same anti-bot page and reset the connection over https. The failure is on access, not availability. A browser fetch of the OAPEN file is the cheapest way to read it. It stays Unfetched until a copy is supplied. |
| LIT-1975 v2 | Adjustable robust solutions of uncertain linear programs | Ben-Tal, Goryashko, Guslitzer and Nemirovski (2004), Math. Program. 99: 351–376. For uncertain LPs with here-and-now and wait-and-see variables, the Adjustable Robust Counterpart (∀ data ∃ adjustment) is never more conservative than the usual Robust Counterpart (∃ one solution ∀ data), coincides with it under constraint-wise uncertainty, and is usually NP-hard. Restricting adjustments to affine functions of the data gives a tractable counterpart for fixed recourse and tight semidefinite approximations otherwise. Each decision may have an information basis, the part of the data it may depend on; in an inventory model, poorer bases raise cost and the non-adjustable counterpart is infeasible. | Active — read 2026-11-03 (NOTE-1503), from the published text on A. Nemirovski’s faculty page; worth reading as the standard distinction between robust (∃ solution ∀ data) and adjustable robust (∀ data ∃ adjustment) decisions, with information bases between them, which CLAIM-537’s conditions I and II instantiate; its own intermediate case is a restriction on the rule’s form (affine), not on what is read. |