We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k>=2 and 1<=r<=k. We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+r). For r = k, we give an analysis of a randomised greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+Sqrt(k/2)). In the case of k=r=2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that NP!=RP. Extending a result of Ando et al., we show that for any k>=3 submodularity in every orthant and pairwise monotonicity (i.e. r=2) precisely characterize k-submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k) for the maximization problem of k-submodular functions.

#### Data Structures for Path Queries

He, Meng ; Munro, J. Ian ; Zhou, GelinWe consider compact routing schemes in networks of low doubling dimension. We consider two variants on routing scheme design: (i) labeled (name-dependent) routing, where the designer is allowed to rename the nodes so that the names (labels) can contain additional, e.g. topological, routing information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, i.e. the node names are independent of the routing scheme. Given any constant µ in (0,1), and an n-node edge-weighted network of doubling dimension ± in o(\loglog n), we present (1) A (1+µ)-stretch labeled compact routing scheme with (log n)-bit routing labels, O(log^2 n/loglog n)-bit packet headers, and O(4^± log^3 n)-bit routing information at each node; (2) A (9+µ)-stretch name-independent compact routing scheme with O(log^2 n/loglog n)-bit packet headers, and O(4^± log^3 n )-bit routing information at each node. In addition, we prove a lower bound: any name-independent routing scheme with o(n^{(µ/60)^2}) bits of storage at each node has stretch no less than 9-µ, for any µ in (0,8). Therefore our name-independent routing scheme achieves asymptotically optimal stretch with polylogarithmic storage at each node and polylogarithmic packet headers. Note that both our schemes are scale-free in the sense that their space requirements do not depend on the normalized diameter of the network. We also present a simpler non-scale-free (9+µ)-stretch name-independent routing scheme with improved space requirements for instances where is polynomial in n.

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the $w$-bit word RAM model. - It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(log n / loglog n). We give an O(n loglog n)-space adaptive data structure that improves the query time to O(loglog n+log k / loglog n), where k is the output count. When k=O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Patrascu, SoCG 2011]. - We give an O(n loglog n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+delta)-factor approximation to the count in O(loglog n) time for any fixed constant delta>0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. - Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jorgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(loglog n + log k / loglog n). We give a new linear-space structure that improves the query time to O(1 + log k / loglog n), exactly matching the lower bound proved by Jorgensen and Larsen.

#### Compressed Cache-Oblivious String B-tree

Ferragina, Paolo ; Venturini, Rossano#### Inapproximability of the Multi-level Uncapacitated Facility Location Problem

Krishnaswamy, Ravishankar ; Sviridenko, MaximWe study the complexity of the Channel Assignment problem. An open problem asks whether Channel Assignment admits an $O(c^n)$-time algorithm, for a constant $c$ independent of the weights on the edges. We answer this question in the negative i.e. we show that there is no $2^{o(n\log n)}$-time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in time $O^*(n!) = 2^{O(n\log n)}$ so our lower bound is tight.

We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree-based database systems do not do it.
We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet access time remains logarithmic in the number of insertions. For many applications of balanced trees, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many if not all classic balanced tree structures. Our structure needs lglg(*m*) + 1 bits of balance information per node, where *m* is the number of insertions and lg is the base-two logarithm, or lglg(*n*) + O(1) with periodic rebuilding, where *n* is the number of nodes. An insertion takes up to two rotations and O(1) amortized time, the same as in standard AVL trees. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node. Our techniques apply to other types of balanced trees, notably B-trees, as we show in a companion paper, and in particular red-black trees, which can be viewed as a special case of B-trees.

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic $2$-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of $3/2$. We complement these upper bounds by proving that they are essentially best possible in the streaming setting: it is shown that an approximation ratio of $2 - \epsilon$ (or $3 / 2 - \epsilon$ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar (J.\ Scheduling 2003) regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

#### Approximation Algorithms for Movement Repairmen

Hajiaghayi, MohammadTaghi ; Khandekar, Rohit ; Khani, Mohammad Reza ; Kortsarz, GuyGiven an $n$-vertex undirected graph $G = (V,E)$ and a parameter $k = 1,2,\ldots$, Thorup-Zwick's distance oracle has size $O(k n^{1+1/k})$, and upon a query $(u,v)$ it constructs a path $\Pi$ between $u$ and $v$ of length $\delta(u,v)$ such that $d_G(u,v) \le \delta(u,v) \le (2k-1) d_G(u,v)$. The query time of this oracle is $O(k)$ (in addition to the length of the returned path), and it was subsequently improved to $O(1)$ \cite{WN12,C14}. A major drawback of the oracle of Thorup and Zwick is that its space is $\Omega(n \cdot \log n)$. Mendel and Naor devised an oracle with space $O(n^{1+1/k})$ and stretch $O(k)$, but their oracle can only report distance estimates and not actual paths. In this paper we devise a path-reporting distance oracle with size $O(n^{1+1/k})$, stretch $O(k)$ and query time $O(n^\eps)$, for an arbitrarily small $\eps > 0$. Another variant of our oracle has size $O(n \log\log n)$, polylogarithmic stretch, and query time $O(\log\log n)$. For unweighted graphs we devise a distance oracle with multiplicative stretch $O(1)$, additive stretch $O(\beta(k))$, for a function $\beta()$, space $O(n^{1+1/k} \cdot \beta)$, and query time $O(n^\eps)$, for an arbitrarily small constant $\eps >0$. The tradeoff between multiplicative stretch and size in these oracles is far below girth conjecture threshold (which is stretch $2k-1$ and size $O(n^{1+1/k})$). An important novel tool that we develop on the way to these results is a {distance-preserving path-reporting oracle}. We believe that this oracle is of independent interest.

#### Gathering Despite Mischief

Dieudonné, Yoann; Pelc, Andrzej; Peleg, David#### Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

Austrin, Per ; Benabbas, Siavosh ; Georgiou, KonstantinosThe dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use no clustering and we allow clients to connect through paths of arbitrary lengths. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.