Abstract: Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an \(O(n\log \log n+ m\log m)\)-time algorithm to compute the geodesic farthest-point Voronoi diagram of m point sites in a simple n-gon. This improves the previously best known algorithm by Aronov et al. (Discrete Comput Geom 9(3):217–255, 1993). In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in \(O((n+m) \log \log n)\) time. PubDate: 2019-11-11

Abstract: The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be \(\textsf {NP}\)-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to \(\textsf {FPT}\) when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set. PubDate: 2019-11-08

Abstract: The parameterised complexity of various consensus string problems (Closest String, Closest Substring, Closest String with Outliers) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance and a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of Closest String and Closest Substring, and partly for Closest String with Outliers; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds. PubDate: 2019-11-04

Abstract: Let \(P \subset \mathbb {R}^d\) be a set of n points in d dimensions such that each point \(p \in P\) has an associated radius \(r_p > 0\) . The transmission graphG for P is the directed graph with vertex set P such that there is an edge from p to q if and only if \( pq \le r_p\) , for any \(p, q \in P\) . A reachability oracle is a data structure that decides for any two vertices \(p, q \in G\) whether G has a path from p to q. The quality of the oracle is measured by the space requirement S(n), the query time Q(n), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in \(O(n \log n)\) time an oracle with \(Q(n) = O(1)\) and \(S(n) = O(n)\) . For planar point sets, the ratio \(\Psi \) between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on \(\Psi \) : the first works only for \(\Psi < \sqrt{3}\) and achieves \(Q(n) = O(1)\) with \(S(n) = O(n)\) and preprocessing time \(O(n\log n)\) ; the second data structure gives \(Q(n) = O(\Psi ^3 \sqrt{n})\) and \(S(n) = O(\Psi ^3 n^{3/2})\) ; the third data structure is randomized with \(Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)\) and \(S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)\) and answers queries correctly with high probability. PubDate: 2019-11-01

Abstract: The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping \(f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m\) such that for any vector \(x \in {\mathbb {R}}^n\) , f preserves its norm to within \((1 {\pm } \varepsilon )\) with probability \(1 - \delta \) if \(m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))\) . Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal \(m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))\) dimensions has an embedding time of \({\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))\) . An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random \(m \times n\) Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in \({\mathcal {O}}(n \lg m)\) time. The big question is of course whether \(m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))\) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that \(m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))\) dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring \(m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))\) for the Toeplitz approach to work. PubDate: 2019-11-01

Abstract: We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graph models. In the Online Preemptive model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms (McGregor, in: Proceedings of the 8th international workshop on approximation, randomization and combinatorial optimization problems, and proceedings of the 9th international conference on randomization and computation: algorithms and techniques, APPROX’05/RANDOM’05, Springer, Berlin, pp. 170–181, 2005; Varadaraja, in: Automata, languages and programming: 38th international colloquium, ICALP 2011, Zurich, Switzerland, proceedings, part I, pp. 379–390, 2011. https://doi.org/10.1007/978-3-642-22006-7_32). Epstein et al. (in: 30th international symposium on theoretical aspects of computer science, STACS 2013, Kiel, Germany, pp. 389–399, 2013. https://doi.org/10.4230/LIPIcs.STACS.2013.389) gave a 5.356-competitive randomized algorithm for MWM, and also proved a lower bound on the competitive ratio of \((1+\ln 2) \approx 1.693\) for MCM. The same lower bound applies for MWM. In the Incremental Graph model, at each step an edge is added to the graph, and the algorithm is supposed to quickly update its current matching. Gupta (in: 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, 15–17 Dec 2014, New Delhi, India, pp. 227–239, 2014. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.227) proved that for any \(\epsilon \le 1/2\) , there exists an algorithm that maintains a \((1+\epsilon )\) -approximate MCM for an incremental bipartite graph in an amortized update time of \(O\left( \frac{\log ^2 n}{\epsilon ^4}\right) \) . No \((2-\epsilon )\) -approximation algorithm with a worst case update time of O(1) is known in this model, even for special classes of graphs. In this paper we show that some of the results can be improved for trees, and for some special classes of graphs. In the online preemptive model, we present a 64 / 33-competitive randomized algorithm (which uses only two bits of randomness) for MCM on trees. Inspired by the above mentioned algorithm for MCM, we present the main result of the paper, a randomized algorithm for MCM with a worst case update time of O(1), in the incremental graph model, which is 3 / 2-approximate (in expectation) on trees, and 1.8-approximate (in expectation) on general graphs with maximum degree 3. Note that this algorithm works only against an oblivious adversary. We derandomize this algorithm, and give a \((3/2+\epsilon )\) -approximate deterministic algorithm for MCM on trees, with an amortized update time of \(O(1/\epsilon )\) . We also present a minor result for MWM in the online preemptive model, a 3-competitive randomized algorithm (that uses only O(1) bits of randomness) on growing trees (where the input revealed upto any stage is always a tree, i.e. a new edge never connects two disconnected trees). PubDate: 2019-11-01

Abstract: We consider a two-way trading problem, where investors buy and sell a stock whose price moves within a certain range. Naturally they want to maximize their profit. Investors can perform up to k trades, where each trade must involve the full amount. We give optimal algorithms for three different models which differ in the knowledge of how the price fluctuates. In the first model, there are global minimum and maximum bounds m and M. We first show an optimal lower bound of \(\varphi \) (where \(\varphi =M/m\) ) on the competitive ratio for one trade, which is the bound achieved by trivial algorithms. Perhaps surprisingly, when we consider more than one trade, we can give a better algorithm that loses only a factor of \(\varphi ^{2/3}\) (rather than \(\varphi \) ) per additional trade. Specifically, for k trades the algorithm has competitive ratio \(\varphi ^{(2k+1)/3}\) . Furthermore we show that this ratio is the best possible by giving a matching lower bound. In the second model, m and M are not known in advance, and just \(\varphi \) is known. We show that this only costs us an extra factor of \(\varphi ^{1/3}\) , i.e., both upper and lower bounds become \(\varphi ^{(2k+2)/3}\) . Finally, we consider the bounded daily return model where instead of a global limit, the fluctuation from one day to the next is bounded, and again we give optimal algorithms, and interestingly one of them resembles common trading strategies that involve stop loss limits. PubDate: 2019-11-01

Abstract: Let \(B=(X,Y,E)\) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC ’98, pp 514–523. https://doi.org/10.1145/276698.276865, 1998; J ACM 49(2):127–138. https://doi.org/10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup’s \(O(n^{120})\) -time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. https://doi.org/10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares. PubDate: 2019-11-01

Abstract: In a recent breakthrough paper Braverman et al. (in: STOC’13, pp 151–160, 2013) developed a local characterization for the zero-error information complexity in the two-party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain natural distributions. Our proof has new components, and in particular, it fixes a minor gap in the proof of Braverman et al. PubDate: 2019-11-01

Abstract: Given a vertex-weighted connected graph \(G = (V, E)\) , the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of \(1/3 - \epsilon \) , for any \(\epsilon > 0\) . In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm. PubDate: 2019-11-01

Abstract: We consider the construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection \(\mathcal {T}\) of texts, where a new symbol may be appended to any text in \(\mathcal {T} = \{T_1, \ldots , T_K\}\) , at any time. This fully-online scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved semi-online text indexing problem, where texts \(T_1, \ldots , T_{k}\) are permanently fixed before the next text \(T_{k+1}\) is processed for each k ( \(1 \le k < K\) ). We first show that a direct application of Weiner’s right-to-left online construction for the suffix tree of a single text to fully-online multiple texts requires superlinear time. This also means that Blumer et al.’s left-to-right online construction for the DAWG of a single text requires superlinear time in the fully-online setting. We then present our fully-online versions of these algorithms that run in \(O(N \log \sigma )\) time and O(N) space, where N is the total length of the texts in \(\mathcal {T}\) and \(\sigma \) is their alphabet size. We then show how to extend Ukkonen’s left-to-right online suffix tree construction to fully-online multiple strings, with the aid of Weiner’s suffix tree for the reversed texts. PubDate: 2019-10-31

Abstract: It is well known that any set of n intervals in \(\mathbb {R} ^1\) admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces. PubDate: 2019-10-31

Abstract: Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. When there is a uniform distribution over the request sequences, this technique reduces to bijective analysis. These methods have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have often provided a clear separation between algorithms whose performance varies significantly in practice. Despite their appealing properties, the above techniques are quite stringent, in that a relation between online algorithms may be either too difficult to establish analytically, or worse, may not even exist. In this paper, we propose remedies to these shortcomings. Our objective is to make all online algorithms amenable to the techniques of stochastic dominance and bijective analysis. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This makes it possible to compare two arbitrary online algorithms for an arbitrary online problem. In addition, the bijective ratio is a generalization of the Max/Max ratio (due to Ben-David and Borodin), and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of O(k) across these metrics. PubDate: 2019-10-29

Abstract: For any integer \(n\ge 1\) , a middle levels Gray code is a cyclic listing of all n-element and \((n+1)\) -element subsets of \(\{1,2,\ldots ,2n+1\}\) such that any two consecutive sets differ in adding or removing a single element. The question whether such a Gray code exists for any \(n\ge 1\) has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. Proc. London Math. Soc., 112(4):677–713, 2016]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. ACM Trans. Algorithms, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time \({{\mathcal {O}}}(n)\) on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time \({{\mathcal {O}}}(1)\) on average, and the required space is \({{\mathcal {O}}}(n)\) . PubDate: 2019-10-25

Abstract: In this article, q-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail: sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input; the amount of esthetic numbers in the first N natural numbers; and the number of odd entries in the rows of Pascal’s rhombus. For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known. PubDate: 2019-10-25

Abstract: A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases \(F=1\) and \(F=2\) . For \(F=1\) , the max–min and min–max problems are solvable in linear time. The case \(F=2\) has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if \(m\ge n-1\) , and a solution always exists in this case, in contrast to \(F=1\) . Moreover, the problem is fixed-parameter tractable in the parameter \(2m-n\) . (Note that this parameter measures the number of agents above the trivial threshold \(m=n/2\) .) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation \(F=2\) to this averaging problem, and some approximation results in cases when m is close to either n or n / 2. PubDate: 2019-10-25

Abstract: We consider the subspace proximity problem: Given a vector \({\varvec{x}} \in {\mathbb {R}}^n\) and a basis matrix \(V \in {\mathbb {R}}^{n \times m}\) , the objective is to determine whether \({\varvec{x}}\) is close to the subspace spanned by V. Although the problem is solvable by linear programming, it is time consuming especially when n is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time independent of n and can be used as a sieve before computing the exact distance between \({\varvec{x}}\) and the subspace. The number of coordinates of \({\varvec{x}}\) queried by our tester is \(O(\frac{m}{\epsilon }\log \frac{m}{\epsilon })\) , where \(\epsilon \) is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets. PubDate: 2019-10-25

Abstract: QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort, Insertionsort and Mergesort. Its major advantage is that QuickXsort can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of QuickXsort in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of QuickXsort and X differ only by o(n)-terms. For median-of-k pivot selection for some constant k, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three QuickMergesort uses at most \(n \lg n - 0.8358n + {\mathcal {O}}(\log n)\) comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to \(n \lg n - 1.4112n + o(n)\) for a remaining gap of only 0.0315n comparisons to the known lower bound (while using only \({\mathcal {O}}(\log n)\) additional space and \({\mathcal {O}}(n\log n)\) time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s Introsort. PubDate: 2019-10-22

Abstract: We introduce a compressed suffix array representation that, on a text T of length n over an alphabet of size \(\sigma \) , can be built in O(n) deterministic time, within \(O(n\log \sigma )\) bits of working space, and counts the number of occurrences of any pattern P in T in time \(O( P + \log \log _w \sigma )\) on a RAM machine of \(w=\Omega (\log n)\) -bit words. This time is almost optimal for large alphabets ( \(\log \sigma =\Theta (\log n)\) ), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require \(\Theta (n\log n)\) bits. For smaller alphabets, where \(\log \sigma = o(\log n)\) , we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time \(O( P /\log _\sigma n + \log _\sigma ^\epsilon n)\) for any constant \(\epsilon >0\) . This is almost RAM-optimal in the typical case where \(w=\Theta (\log n)\) . PubDate: 2019-10-22