# Algorithmica

### Logit Dynamics with Concurrent Updates for Local Interaction Potential Games

*Logit choice* dynamics constitute a family of randomized best response dynamics based on the *logit choice function* (McFadden in Frontiers in econometrics. Academic Press, New York, 1974) that models players with limited rationality and knowledge. In this paper we study the *all-logit dynamics* [also known as *simultaneous learning* (Alós-Ferrer and Netzer in Games Econ Behav 68(2):413–427, 2010)], where at *each* time step *all* players *concurrently* update their strategies according to the logit choice function. In the well studied *(one-)logit dynamics* (Blume in Games Econ Behav 5(3):387–424, 1993) instead at each step *only one* randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of *local interaction potential games*, a class of games that has been used to model complex social phenomena (Montanari and Saberi 2009; Peyton in The economy as a complex evolving system. Oxford University Press, Oxford, 2003) and physical systems (Levin et al. in Probab Theory Relat Fields 146(1–2):223–265, 2010; Martinelli in Lectures on probability theory and statistics. Springer, Berlin, 1999). In a local interaction potential game players are the vertices of a *social graph* whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction potential games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call *decomposable* observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the *rationality* level
\(\beta \)
and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level
\(\beta \)
, whereas for other games it can be upper bounded by a function independent from
\(\beta \)
.

### Computing the Greedy Spanner in Linear Space

The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner on \(n\) points use \(\varOmega (n^2)\) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a linear-space algorithm that computes the same spanner for points in \(\mathbb {R}^d\) running in \(O(n^2 \log ^2 n)\) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

### Binary Jumbled Pattern Matching on Trees and Tree-Like Structures

Binary jumbled pattern matching asks to preprocess a binary string \(S\) in order to answer queries \((i,j)\) which ask for a substring of \(S\) that is of length \(i\) and has exactly \(j\) 1-bits. This problem naturally generalizes to vertex-labeled trees and graphs by replacing “substring” with “connected subgraph”. In this paper, we give an \(O(n^2 / \log ^2 n)\) -time solution for trees, matching the currently best bound for (the simpler problem of) strings. We also give an \({O}({g^{2 / 3} n^{4 / 3}/(\log n)^{4/3}})\) -time solution for strings that are compressed by a context-free grammar of size \(g\) in Chomsky normal form. This solution improves the known bounds when the string is compressible under many popular compression schemes. Finally, we prove that on graphs the problem is fixed-parameter tractable with respect to the treewidth \(w\) of the graph, even for a constant number of different vertex-labels, thus improving the previous best \(n^{O(w)}\) algorithm.

### The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

Persistent homology with coefficients in a field \(\mathbb {F}\) coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

### A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems

We consider the smoothed analysis of Euclidean optimization problems. Here, input points are sampled according to density functions that are bounded by a sufficiently small smoothness parameter \(\phi \) . For such inputs, we provide a general and systematic approach that allows designing linear-time approximation algorithms whose output is asymptotically optimal, both in expectation and with high probability. Applications of our framework include maximum matching, maximum TSP, and the classical problems of k-means clustering and bin packing. Apart from generalizing corresponding average-case analyses, our results extend and simplify a polynomial-time probable approximation scheme on multidimensional bin packing on \(\phi \) -smooth instances, where \(\phi \) is constant (Karger and Onak in Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems, pp 1207–1216, 2007). Both techniques and applications of our rounding-based approach are orthogonal to the only other framework for smoothed analysis of Euclidean problems we are aware of (Bläser et al. in Algorithmica 66(2):397–418, 2013).

### A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

We consider a two-edge connected, non-negatively real-weighted graph *G* with *n* vertices and *m* edges, and a single-source shortest paths tree (SPT) of *G* rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a *swap edge*. This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a *best* possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the *maximum* or the *average* distance between the root and the disconnected vertices. For the former criteria, we present an
\(O(m \log \alpha (m,n))\)
time algorithm—where
\(\alpha \)
is the inverse of the Ackermann function—to find a best swap edge for *every* edge of the SPT, thus improving onto the previous
\(O(m \log n)\)
time algorithm. Concerning the latter criteria, we provide an
\(O(m+n \log n)\)
time algorithm for the special but important case where *G* is *unweighted*, which compares favourably with the
\(O\left( m+n \, \alpha (n,n)\log ^2n\right) \)
time bound that one would get by using the fastest algorithm known for the weighted case—once this is suitably adapted to the unweighted case.

### Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines

In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered
\(L_p, p<\infty \)
norms. Our main results are: (1) we give an
\(\mathcal {O}({\varepsilon }^{-3})\)
-competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process
\(1+{\varepsilon }\)
units of a job in 1 time-unit (
\({\varepsilon }\)
speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple
\(2/{\varepsilon }\)
-competitive algorithm when we augment the speed by
\({\varepsilon }\)
. For *m* machines we show a lower bound of
\({\varOmega }(m)\)
on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this “drawback” we show a lower bound of
\({\varOmega }(\log m)\)
on the competitive ratio of *immediate dispatch* algorithms. In both these lower bound constructions we use jobs whose processing times are in
\(\left\{ 1,\infty \right\} \)
, and hence they apply to the more restrictive *subset parallel* setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of
\({\varOmega }(\log m)\)
-on the competitive ratio of any online algorithm which is permitted to use
\(s=\mathcal {O}(1)\)
speed machines. In our lower bound construction, job *j* has a processing time of
\(p_j\)
on a subset of machines and infinity on others and has a weight
\(1/p_j\)
. Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.

### Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

We show that the quantum query complexity of detecting if an *n*-vertex graph contains a triangle is
\(O(n^{9/7})\)
. This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012) making
\(O(n^{35/27})\)
queries. For the problem of determining if an operation
\(\circ : S \times S \rightarrow S\)
is associative, we give an algorithm making
\(O(|S|^{10/7})\)
queries, the first improvement to the trivial
\(O(|S|^{3/2})\)
application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm.

### Computing Approximate Nash Equilibria in Polymatrix Games

In an
\(\epsilon \)
-Nash equilibrium, a player can gain at most
\(\epsilon \)
by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known
\(\epsilon \)
achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365–382, 2008). In general, for *n*-player games an
\(\epsilon \)
-Nash equilibrium can be computed in polynomial time for an
\(\epsilon \)
that is an increasing function of *n* but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of
\(\epsilon \)
are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general *n*-player games where a player’s payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant
\(\epsilon \)
such that computing an
\(\epsilon \)
-Nash equilibrium of a polymatrix game is
\(\mathtt {PPAD}\)
-hard. Our main result is that a
\((0.5+\delta )\)
-Nash equilibrium of an *n*-player polymatrix game can be computed in time polynomial in the input size and
\(\frac{1}{\delta }\)
. Inspired by the algorithm of Tsaknakis and Spirakis [28], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a
\((0.5+\delta )\)
-Nash equilibrium in a two-player Bayesian game.

### An Optimal Algorithm for the Weighted Backup 2-Center Problem on a Tree

In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex *u* to *v* is weighted by the weight of *u*. With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.

### Improved Subquadratic 3SUM

In the 3SUM problem we are given three lists
\(\mathcal {A}\)
,
\(\mathcal {B}\)
,
\(\mathcal {C}\)
, of *n* real numbers, and are asked to find
\((a,b,c)\in \mathcal {A}\times \mathcal {B}\times \mathcal {C}\)
such that
\(a+b=c\)
. The longstanding *3SUM conjecture*—that 3SUM could not be solved in subquadratic time—was recently refuted by Grønlund and Pettie. They presented
\(\hbox {O}\left( n^2(\log \log n)^{\alpha }/(\log n)^{\beta }\right) \)
algorithms for 3SUM and for the related problems Convolution3SUM and ZeroTriangle, where
\(\alpha \)
and
\(\beta \)
are constants that depend on the problem and whether the algorithm is deterministic or randomized (and for ZeroTriangle the main factor is
\(n^3\)
rather than
\(n^2\)
). We simplify Grønlund and Pettie’s algorithms and obtain better bounds, namely,
\(\alpha =\beta =1\)
, deterministically. For 3SUM our bound is better than both the deterministic and the randomized bounds of Grønlund and Pettie. For the other problems our bounds are better than their deterministic bounds, and match their randomized bounds.

### Exact Sublinear Binomial Sampling

Drawing a random variate from a given binomial distribution *B*(*n*, *p*) is an important subroutine in many large-scale simulations. The naive algorithm takes
\(\mathcal {O}(n)\)
time w.h.p. in the WordRAM model, which is too slow in many settings, though to its credit, it does not suffer from precision loss. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [22] and the GNU Scientific Library [11], however, all previous sublinear-time algorithms involve precision loss, which introduces artifacts such as discontinuities into the sampling. In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss. We assume that each bit of *p* can be obtained in
\(\mathcal {O}(1)\)
time.

### A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3.

### Resilient Dynamic Programming

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults at any level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.

### Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints

We introduce a new structure for a set of points in the plane and an angle
\(\alpha \)
, which is similar in flavor to a bounded-degree MST. We name this structure
\(\alpha \)
-MST. Let *P* be a set of points in the plane and let
\(0 < \alpha \le 2\pi \)
be an angle. An
\(\alpha \)
-ST of *P* is a spanning tree of the complete Euclidean graph induced by *P*, with the additional property that for each point
\(p \in P\)
, the smallest angle around *p* containing all the edges adjacent to *p* is at most
\(\alpha \)
. An
\(\alpha \)
-MST of *P* is then an
\(\alpha \)
-ST of *P* of minimum weight, where the weight of an
\(\alpha \)
-ST is the sum of the lengths of its edges. For
\(\alpha < \pi /3\)
, an
\(\alpha \)
-ST does not always exist, and, for
\(\alpha \ge \pi /3\)
, it always exists (Ackerman et al. in Comput Geom Theory Appl 46(3):213–218, 2013; Aichholzer et al. in Comput Geom Theory Appl 46(1):17–28, 2013; Carmi et al. in Comput Geom Theory Appl 44(9):477–485, 2011). In this paper, we study the problem of computing an
\(\alpha \)
-MST for several common values of
\(\alpha \)
. Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point
\(p \in P\)
, we associate a wedge
\({\textsc {w}_{p}}\)
of angle
\(\alpha \)
and apex *p*. The goal is to assign an orientation and a radius
\(r_p\)
to each wedge
\({\textsc {w}_{p}}\)
, such that the resulting graph is connected and its MST is an
\(\alpha \)
-MST (we draw an edge between *p* and *q* if
\(p \in {\textsc {w}_{q}}\)
,
\(q \in {\textsc {w}_{p}}\)
, and
\(|pq| \le r_p, r_q\)
). We prove that the problem of computing an
\(\alpha \)
-MST is NP-hard, at least for
\(\alpha =\pi \)
and
\(\alpha =2\pi /3\)
, and present constant-factor approximation algorithms for
\(\alpha = \pi /2, 2\pi /3, \pi \)
. One of our major results is a surprising theorem for
\(\alpha = 2\pi /3\)
, which, besides being interesting from a geometric point of view, has important applications. For example, the theorem guarantees that given *any* set *P* of 3*n* points in the plane and *any* partitioning of the points into *n* triplets, one can orient the wedges of each triplet *independently*, such that the graph induced by *P* is connected. We apply the theorem to the *antenna conversion* problem and to the *orientation and power assignment* problem.

### Editorial

### Regular Augmentation of Planar Graphs

In this paper, we study the problem of augmenting a planar graph such that it becomes \(k\) -regular, \(c\) -connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. We fully classify the complexity of this problem for all values of \(k\) and \(c\) in both, the variable embedding and the fixed embedding case. For \(k \le 2\) all problems are simple and for \(k \ge 4\) all problems are NP-complete. Our main results are efficient algorithms (with running time \(O(n^{1.5}))\) for deciding the existence of a \(c\) -connected, 3-regular augmentation of a graph with a fixed planar embedding for \(c=0,1,2\) and a corresponding hardness result for \(c=3\) . The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time.

### What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid

We design a sublinear Fourier sampling algorithm for a case of sparse *off-grid* frequency recovery. These are signals with the form
\(f(t) = \sum _{j=1}^k a_j \mathrm{e}^{i\omega _j t} + \int \nu (\omega )\mathrm{e}^{i\omega t}d\mu (\omega )\)
; i.e., exponential polynomials with a noise term. The frequencies
\(\{\omega _j\}\)
satisfy
\(\omega _j\in [\eta ,2\pi -\eta ]\)
and
\(\min _{i\ne j} |\omega _i-\omega _j|\ge \eta \)
for some
\(\eta > 0\)
. We design a sublinear time randomized algorithm which, for any
\(\epsilon \in (0,\eta /k]\)
, which takes
\(O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))\)
samples of
\(f(t)\)
and runs in time proportional to number of samples, recovering
\(\omega _j'\approx \omega _j\)
and
\(a_j'\approx a_j\)
such that, with probability
\(\varOmega (1)\)
, the approximation error satisfies
\(|\omega _j'-\omega _j|\le \epsilon \)
and
\(|a_j-a_j'|\le \Vert \nu \Vert _1/k\)
for all
\(j\)
with
\(|a_j|\ge \Vert \nu \Vert _1/k\)
. We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.

### Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties

We consider the *facility location problem with submodular penalties* (FLPSP) and the *facility location problem with linear penalties* (FLPLP), two extensions of the classical *facility location problem* (FLP). First, we introduce a general algorithmic framework for a class of covering problems with *submodular* penalties, extending the recent result of Geunes et al. (Math Program 130:85–106, 2011) with *linear* penalties. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their counterparts with submodular penalties. Specifically, any LP-based
\(\alpha \)
-approximation for the original covering problem can be leveraged to obtain an
\(\left( 1-e^{-1/\alpha }\right) ^{-1}\)
-approximation algorithm for the counterpart with submodular penalties. Consequently, any LP-based approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the counterpart with submodular penalties. Second, by exploiting some special properties of submodular/linear penalty function, we present an LP rounding algorithm which has the currently best
\(2\)
-approximation ratio over the previously best
\(2.375\)
by Li et al. (Theoret Comput Sci 476:109–117, 2013) for the FLPSP and another LP-rounding algorithm which has the currently best
\(1.5148\)
-approximation ratio over the previously best
\(1.853\)
by Xu and Xu (J Comb Optim 17:424–436, 2008) for the FLPLP, respectively.