operations-research.
26 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-015 v2 | Periodic vehicle routing and facility location for waste collection | 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. | Read |
| NOTE-062 v2 | Başar, Meyn & Perkins, control system theory notes | 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. | Read |
| NOTE-068 v2 | Tembine et al., mean-field-type games with Rosenblatt noise | 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. | Read |
| NOTE-276 | A numerical algorithm for block-diagonal decomposition of matrix *-algebras with application to semidefinite programming | 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. | Read |
| NOTE-676 | Generalized Information-Theoretic Tree Abstractions (G-tree search) | Proves that when the encoder is a pruning of a fixed quadtree, any weighted sum of relevant-information, irrelevant-information and compression terms splits over interior nodes, so a bottom-up recursion finds the optimal tree with fewest leaves exactly, in linear time, where greedy splitting can miss everything. The tree solving IB with side information is always a pruning of the plain IB tree for the same β. | Read |
| NOTE-889 | Gupta — Selection of views to materialize in a data warehouse | 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. | Read |
| NOTE-890 | Gupta & Mumick — Selection of views to materialize under a maintenance cost constraint | 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. | Read |
| NOTE-895 | Harinarayan, Rajaraman & Ullman — Implementing data cubes efficiently | 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. | Read |
| NOTE-898 | Finkelstein, Schkolnick & Tiberio — Physical database design for relational databases | 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. | Read |
| NOTE-900 | Chaudhuri & Narasayya — An efficient, cost-driven index selection tool for Microsoft SQL Server | 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. | Read |
| NOTE-901 | Gupta & Mumick — Selection of views to materialize in a data warehouse (TKDE 2005) | 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. | Read |
| NOTE-906 | Cho & Garcia-Molina — Synchronizing a database to improve freshness (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. | Read |
| NOTE-908 | Labrinidis & Roussopoulos — WebView materialization | 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. | Read |
| NOTE-911 | Labrinidis & Roussopoulos — Balancing performance and data freshness in web database servers | 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. | Read |
| NOTE-912 | Olston, Loo & Widom — Adaptive precision setting for cached approximate values | 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. | Read |
| NOTE-922 | Olston & Widom — Offering a precision-performance tradeoff for aggregation queries over replicated data | 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. | Read |
| NOTE-928 | Linial, London & Rabinovich — the geometry of graphs | Every n-point metric embeds in ℓ₂ with distortion O(log n) in O(log n) dimensions (Theorem 3.2(1), attributed to Bourgain). The paper reproves the distortion bound by a randomized Bourgain-style construction into ℓ_p^{O(log² n)}, and it gets the dimension from Johnson–Lindenstrauss. Every embedding of a constant-degree expander into ℓ_p, 1 ≤ p ≤ 2, of any dimension, has distortion Ω(log n) (Proposition 4.2), so the bound is tight. The lower bound comes from Leighton and Rao’s flow–cut gap, and the same embeddings give an O(log k) max-flow/min-cut gap for k commodities. | Read |
| NOTE-1072 | FEMA — National Incident Management System, third edition | The U.S. national doctrine for incident management. The parts read establish a single command function (one Incident Commander, or a Unified Command in which “there is no one ‘commander.’” and each agency keeps its own authority), unity of command, modular delegation, a briefed transfer of command, and a Safety Officer who “alters, suspends, or terminates any activities that are immediately dangerous to life and health”. It is doctrine, stating how incidents should be organized, not evidence of how they are. | Skimmed |
| NOTE-1073 | Jensen Hughes — Post-incident analysis of the Brookhollow Apartment fire | An independent review, commissioned by Sedgwick County and Wichita, of every public-safety agency’s response to the fire of 13 October 2023 that killed Paoly Bedeski. It found “no single point of failure” but “systemic shortcomings that, when combined, contributed to an unorganized rescue effort”: a dispatcher who did not replay her unit number, an 18-minute delay in the second alarm, no effective command, freelancing, search not resumed for over eleven minutes after a mayday that was under control within minutes, and Wichita Fire Department policies that existed and were not followed. It could not conclude the shortcomings changed the outcome. | Read |
| NOTE-1086 | NTSB — United Airlines Flight 173, Portland, 1978 | The NTSB found that United 173 ran out of fuel after holding about an hour near Portland while its crew dealt with a landing-gear problem, that fuel exhaustion “was predictable”, and that the probable cause was the captain’s failure to monitor the fuel state and respond to the crew’s advisories. The other two crew members either did not grasp the criticality or did not communicate it; no one was assigned to watch the fuel. It recommended indoctrination in “flightdeck resource management”, with “participative management for captains and assertiveness training for other cockpit crewmembers”. | Read |
| NOTE-1087 | Helmreich, Merritt & Wilhelm — The evolution of Crew Resource Management training | A short history and argument. CRM began with a 1979 NASA workshop and United’s 1981 program, and passed through five “generations”, from managerial-style seminars to integration with technical training under the FAA’s AQP. Its effects are hard to validate (accident rates cannot be used), acceptance of its concepts decays over time even with recurrent training, and it exported poorly across cultures. The authors propose error management (avoid, trap, mitigate) as a rationale all pilots can accept. Command is mentioned only in passing. | Read |
| NOTE-1088 | GAO — NASA: better mechanisms needed for sharing lessons learned | A 2001 survey of NASA’s 192 program and project managers (115 usable responses, 60 percent) found that NASA’s policies required lessons to be reviewed and submitted, but managers did not routinely identify, collect or share them, its Lessons Learned Information System was little used, and NASA recorded how often the system was searched but not whether any lesson was applied, so “NASA has no assurance that lessons are being applied”. The occasion was the 1999 Mars failures, not Challenger. | Read |
| NOTE-1090 | Rogers Commission — Report on the Space Shuttle Challenger accident | The presidential commission’s account of Challenger. The physical cause was a field-joint seal design “unacceptably sensitive” to temperature and other factors; the contributing cause was a “flawed” launch decision in which Thiokol’s engineers’ recommendation against launch was reversed by Thiokol management “at the urging of Marshall”, and neither that dispute, the July 1985 launch constraint nor its six waivers reached Levels I and II. The joint had a nine-year history of warnings, accepted erosion and loosened criteria, and the safety, reliability and quality-assurance function was understaffed, subordinate to the offices it checked, and absent from the decision. | Skimmed |
| NOTE-1356 | Castro and Liskov — Practical Byzantine fault tolerance | A state-machine replication protocol that keeps safety with at most ⌊(n − 1)/3⌋ arbitrarily faulty replicas and no timing assumption, needing weak synchrony only for liveness; a three-phase commit within views and a view change that carries prepared requests forward. With MACs in place of signatures, a replicated NFS ran the Andrew benchmark 3% slower than Digital Unix’s NFS on four replicas, with view changes not yet implemented in the measured library. | Read |
| NOTE-1401 | Désidéri — Multiple-gradient descent algorithm (MGDA) | Defines Pareto-stationarity (some convex combination of the criteria’s gradients is zero), proves it necessary for Pareto-optimality, and shows that when it fails the minimum-norm element ω of the gradients’ convex hull gives a direction −ω along which every criterion decreases, with (u, ω) ≥ ‖ω‖² for every u in the hull. Steepest descent along −ω, the MGDA, has a subsequence converging to a Pareto-stationary point when the criteria are positive and coercive. The direction depends on how the gradients are scaled; the author calls the right scaling open. | Read |
| NOTE-1503 | Ben-Tal, Goryashko, Guslitzer & Nemirovski — Adjustable robust solutions | For an uncertain LP whose variables split into here-and-now ones and adjustable ones chosen after the data are revealed, the Adjustable Robust Counterpart (∀ data ∃ adjustment) can be much less conservative than the usual Robust Counterpart (∃ one solution ∀ data); they coincide under constraint-wise uncertainty. The ARC is usually NP-hard; restricting adjustments to affine functions of the data (AARC) is tractable with fixed recourse. Each variable may have an information basis, a prescribed portion of the data it can depend on; in an inventory example, poorer information bases raise cost and the non-adjustable RC is infeasible. | Read |