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.
6 of 371 QUESTION documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| QUESTION-114 | Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks? | The LEGO parable (CASE-094) is QUESTION-095’s trade in its plainest form. Sorting spends search once, against retrievals later, and leaves the result in the world, as the cockpit’s speed bugs do. CLAIM-310 adds that one set of bins realizes one partition, chosen against a query mix. A database table is stored in one physical order, and every further index costs space and work on every insert. Choosing indexes for a workload is a studied problem with explicit cost models. This asks whether that model is the one QUESTION-095 is looking for. | Open |
| QUESTION-194 | How far is a periodic greedy that switches a capped number of page fragments between caching and materializing, to keep the share of fresh fragments served above a threshold, from the best plan that meets the same threshold? | The promotion condition formerly on THEORY-382. THEORY-382 was promoted on 2026-10-19 (ADR-047 v3) on what Labrinidis and Roussopoulos measured: in one synthetic simulation with fixed costs, their OVIS greedy tracked the freshness threshold, answered faster than caching alone and recovered from overload. No run compares it with the best plan, and its optimality under the cap is asserted, not proved. | Open |
| QUESTION-224 | Is Bruno and Chaudhuri’s single-index online tuner within some constant, such as 3 + 2f, of the offline optimum on every workload whose per-statement savings and losses are at most a fraction f of the build cost? | The promotion condition formerly on THEORY-332. THEORY-332 was promoted on 2026-10-20 (ADR-047 v2) for the lower bound its construction proves: with every step at most fB, Online-SI can cost nearly 3 + 2f times the optimum, and one step above B makes the ratio unbounded. Whether any constant bounds it from above on such workloads is open. | Open |
| QUESTION-227 | Does the widen-on-push, narrow-on-fetch rule for a cached interval’s width converge to within a stated factor of the best fixed width, and does it hold its cost against the best fixed width and an adaptive cache-or-not rule on data other than its authors’ traces? | The promotion condition formerly on THEORY-377. THEORY-377 was narrowed to Olston, Loo and Widom’s simulations and promoted on 2026-10-20 (ADR-047 v3). Whether their width-setting rule converges, and whether it holds up on other data, is open. | Open |
| QUESTION-340 | When does a cache replacement value based on distance from the current query beat recency-based eviction: does a competitive analysis, or an analysis under a stated distribution of query paths, say so, and do experiments in another system that vary cycle length relative to cache size recover the crossover with MRU? | The promotion condition formerly on THEORY-375, moved here when the status review of 2026-10-30 promoted it under ADR-065. Dar et al.’s crossover between distance and MRU is simulated on synthetic paths and not explained. | Open |
| QUESTION-347 | On another database and web stack with native materialized views and queries of graded cost, does a stored query result kept current on every update lose to recomputation exactly when reading it costs about as much as recomputing it and its refresh runs on the resource that serves requests, and win otherwise? | The promotion condition formerly on THEORY-383, moved here when the status review of 2026-10-30 promoted it under ADR-065. Labrinidis and Roussopoulos measured one testbed with cheap indexed selections; their cost model’s Eq. 9 was never evaluated against measurement. | Open |