Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost , where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant.

Osborne's iteration is a method for balancing $n\times n$ matrices which is widely used in linear algebra packages, as balancing preserves eigenvalues and stabilizes their numeral computation. The iteration can be implemented in any norm over $\mathbb{R}^n$, but it is normally used in the $L_2$ norm. The choice of norm not only affects the desired balance condition, but also defines the iterated balancing step itself. In this paper we focus on Osborne's iteration in any $L_p$ norm, where $p < \infty$. We design a specific implementation of Osborne's iteration in any $L_p$ norm that converges to a strictly $ε$-balanced matrix in $\tilde{O}(ε^{-2}n^{9} K)$ iterations, where $K$ measures, roughly, the {\em number of bits} required to represent the entries of the input matrix. This is the first result that proves that Osborne's iteration in the $L_2$ norm (or any $L_p$ norm, $p < \infty$) strictly balances matrices in polynomial time. This is a substantial improvement over our recent result (in SODA 2017) that showed weak balancing in $L_p$ norms. Previously, Schulman and Sinclair (STOC 2015) showed strong balancing of Osborne's iteration in the $L_\infty$ norm. Their result does not imply any bounds on strict balancing in other norms.

We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. The original algorithm was proposed for balancing rows and columns in the L2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne's algorithm that uses the L∞ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the L1 norm and other Lp norms. We show the following results for any matrix , resolving in particular a main open problem mentioned by Schulman and Sinclair. 1. We analyze the iteration for the L1 norm under a greedy order of balancing. We show that it converges to an ∊-balanced matrix in K = O(min{ ∊−2 log w, ∊−1n3/2 log(w / ∊)}) iterations that cost a total of O(m + Kn log n) arithmetic operations over O(n log(w/∊))-bit numbers. Here m is the number of non-zero entries of A, and w =∑i,j |aij|/amin with amin = min{|aij| : aj ≠ 0}. 2. We show that the original round-robin implementation converges to an ∊ -balanced matrix in O(∊−2n2 log w) iterations totaling O(∊−2mn log w) arithmetic operations over O(nlog(w/∊))-bit numbers. 3. We show that a random implementation of the iteration converges to an ∊ -balanced matrix in O(∊−2 log w) iterations using O(m + ∊−2n log w) arithmetic operations over O(log(wn/∊))-bit numbers. 4. We demonstrate a lower bound of on the convergence rate of any implementation of the iteration. 5. We observe, through a known trivial reduction, that our results for L1 balancing apply to any Lp norm for all finite p, at the cost of increasing the number of iterations by only a factor of p. We note that our techniques are very different from those used by Schulman and Sinclair.

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1--14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: for an LP formulation due to Dantzig et al. (1985): (i) the integrality gap is bounded by a constant; (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.