Authors:Cristina G. Fernandes; Rafael C. S. Schouery Pages: 2973 - 2992 Abstract: Abstract We consider the Max-Buying Problem with Limited Supply, in which there are n items, with \(C_i\) copies of each item i, and m consumers such that each consumer b has a valuation \(v_{ib}\) for item i. The goal is to find a pricing p and an allocation of items to consumers that maximize the revenue, with every item allocated to at most \(C_i\) consumers, every consumer receives at most one item, and if a consumer b receives item i, then \(p_i \le v_{ib}\) . We present a randomized \(e/(e-1)\) -approximation for the Max-Buying Problem with Limited Supply and show how to derandomize it, improving the previously known upper bound of 2. The algorithm uses an integer programming formulation with an exponential number of variables to do a probabilistic rounding and it explores some structure of the problem that might be useful when developing approximations for other pricing problems. We also present a PTAS for the price ladder variant, in which the pricing must be non-increasing (that is, \(p_1 \ge p_2 \ge \cdots \ge p_n\) ), improving the previously known upper bound of 4. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0364-7 Issue No:Vol. 80, No. 11 (2018)

Authors:Leo van Iersel; Steven Kelk; Georgios Stamoulis; Leen Stougie; Olivier Boes Pages: 2993 - 3022 Abstract: Abstract The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0366-5 Issue No:Vol. 80, No. 11 (2018)

Authors:Maitri Chakraborty; Alessia Milani; Miguel A. Mosteiro Pages: 3023 - 3049 Abstract: Abstract We study the problem of Counting the number of nodes in Anonymous Dynamic Network: nodes do not have identifiers and the network topology changes frequently. Counting is a fundamental task in distributed computing, for instance, to decide termination. Knowing what is the cost of anonymity is of paramount importance to understand what is feasible for future generations of Dynamic Networks, where the lack of nodes identifiers might facilitate mass production. Previous upper bounds to compute the exact network size are double-exponential. Strikingly, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this work, we achieve an exponential speedup presenting Incremental Counting (IC), a distributed Counting protocol for Anonymous Dynamic Networks that has exponential time complexity and computes the exact size of the system. We complement the theoretical study evaluating IC experimentally. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. Our simulations showed that IC is polynomial for all the inputs tested, paving the way to use it in practical applications where the network topology is predictable. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0367-4 Issue No:Vol. 80, No. 11 (2018)

Authors:Paz Carmi; Lilach Chaitman-Yerushalmi; Ohad Trabelsi Pages: 3050 - 3077 Abstract: Abstract We study the problem of assigning transmission ranges to radio stations in the plane such that any pair of stations can communicate within a bounded number of hops h and the cost of the network is minimized. We consider two settings of the problem: collinear station locations and arbitrary locations. For the case of collinear stations, we introduce the pioneer polynomial-time exact algorithm for any \(\alpha \ge 1\) and constant h, and thus conclude that the 1D version of the problem, where h is a constant, is in \(\mathcal {P}\) . Furthermore, we provide a 3 / 2-approximation algorithm for the case where h is an arbitrary number and \(\alpha =1\) , improving the previously best known approximation ratio of 2. For the case of stations placed arbitrarily in the plane and \(\alpha =1\) , we first present a \((1.5+ \varepsilon )\) -approximation algorithm for a case where a deviation of one hop ( \(h+1\) hops in total) is acceptable. Then, we show a \((3+\varepsilon )\) -approximation algorithm that complies with the exact hop bound. To achieve that, we introduce the following two auxiliary problems, which are of independent interest. The first is the bounded-hop multi-sink range problem, for which we present a PTAS which can be applied to compute a \((1+\varepsilon )\) -approximation for the bounded diameter minimum spanning tree, for any \(\varepsilon >0\) . The second auxiliary problem is the bounded-hop dual-sink pruning problem, for which we show a polynomial-time algorithm. To conclude, we consider the initial bounded-hop all-to-all range assignment problem and show that a combined application of the aforementioned problems yields the \((3+\varepsilon )\) -approximation ratio for this problem, which improves the previously best known approximation ratio of \(4(9^{h-2})/(\root h \of {2}-1)\) . PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0370-9 Issue No:Vol. 80, No. 11 (2018)

Authors:Vincenzo Auletta; Diodato Ferraioli; Francesco Pasquale; Giuseppe Persiano Pages: 3078 - 3131 Abstract: Abstract Logit dynamics (Blume in Games Econ Behav 5:387–424, 1993) are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. It can happen that the chain is “metastable”, i.e., on a time-scale shorter than the mixing time, it stays close to some probability distribution over the state space, while in a time-scale multiple of the mixing time it jumps from one distribution to another. In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the logit dynamics for some classes of coordination games. We first consider a pure n-player coordination game that highlights the distinctive features of our metastability notion based on distributions. Then, we study coordination games on the clique without a risk-dominant strategy (which are equivalent to the well-known Glauber dynamics for the Curie–Weiss model) and coordination games on a ring (both with and without risk-dominant strategy). PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0371-8 Issue No:Vol. 80, No. 11 (2018)

Authors:Endre Boros; Khaled Elbassioni; Mahmoud Fouz; Vladimir Gurvich; Kazuhisa Makino; Bodo Manthey Pages: 3132 - 3157 Abstract: Abstract We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0372-7 Issue No:Vol. 80, No. 11 (2018)

Authors:Wenchang Luo; Yao Xu; Boyuan Gu; Weitian Tong; Randy Goebel; Guohui Lin Pages: 3158 - 3176 Abstract: Abstract We consider a communication scheduling problem that arises within wireless sensor networks, where data is accumulated by the sensors and transferred directly to a central base station. One may choose to compress the data collected by a sensor, to decrease the data size for transmission, but the cost of compression must be considered. The goal is to designate a subset of sensors to compress their collected data, and then to determine a data transmission order for all the sensors, such that the total compression cost is minimized subject to a bounded data transmission completion time (a.k.a. makespan). A recent result confirms the NP-hardness for this problem, even in the special case where data compression is free. Here we first design a pseudo-polynomial time exact algorithm, articulated within a dynamic programming scheme. This algorithm also solves a variant with the complementary optimization goal—to minimize the makespan while constraining the total compression cost within a given budget. Our second result consists of a bi-factor \((1 + \epsilon , 2)\) -approximation for the problem, where \((1 + \epsilon )\) refers to the compression cost and 2 refers to the makespan, and a 2-approximation for the variant. Lastly, we apply a sparsing technique to the dynamic programming exact algorithm, to achieve a dual fully polynomial time approximation scheme for the problem and a usual fully polynomial time approximation scheme for the variant. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0373-6 Issue No:Vol. 80, No. 11 (2018)

Authors:Ahmad Biniaz; Prosenjit Bose; David Eppstein; Anil Maheshwari; Pat Morin; Michiel Smid Pages: 3177 - 3191 Abstract: Abstract Let R and B be two disjoint sets of points in the plane where the points of R are colored red and the points of B are colored blue, and let \(n= R\cup B \) . A bichromatic spanning tree is a spanning tree in the complete bipartite geometric graph with bipartition (R, B). The minimum (respectively maximum) bichromatic spanning tree problem is the problem of computing a bichromatic spanning tree of minimum (respectively maximum) total edge length. (1) We present a simple algorithm that solves the minimum bichromatic spanning tree problem in \(O(n\log ^3 n)\) time. This algorithm can easily be extended to solve the maximum bichromatic spanning tree problem within the same time bound. It also can easily be generalized to multicolored point sets. (2) We present \(\Theta (n\log n)\) -time algorithms that solve the minimum and the maximum bichromatic spanning tree problems. (3) We extend the bichromatic spanning tree algorithms and solve the multicolored version of these problems in \(O(n\log n\log k)\) time, where k is the number of different colors (or the size of the multipartition in a complete multipartite geometric graph). PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0375-4 Issue No:Vol. 80, No. 11 (2018)

Authors:Peyman Afshani; Konstantinos Tsakalidis Pages: 3192 - 3206 Abstract: Abstract Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in \(O\left( n\log n\right) \) worst-case time, using \(O\left( n\right) \) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0376-3 Issue No:Vol. 80, No. 11 (2018)

Authors:Philip Bille; Anders Roy Christiansen; Patrick Hagge Cording; Inge Li Gørtz; Frederik Rye Skjoldjensen; Hjalte Wedel Vildhøj; Søren Vind Pages: 3207 - 3224 Abstract: Abstract Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string S is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0380-7 Issue No:Vol. 80, No. 11 (2018)

Authors:Alok Baveja; Amit Chavan; Andrei Nikiforov; Aravind Srinivasan; Pan Xu Pages: 3225 - 3252 Abstract: Abstract Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0383-4 Issue No:Vol. 80, No. 11 (2018)

Authors:Mark de Berg; Joachim Gudmundsson; Ali D. Mehrabi Pages: 3253 - 3269 Abstract: Abstract We study the following problem: preprocess a set \(\mathcal {O}\) of objects into a data structure that allows us to efficiently report all pairs of objects from \(\mathcal {O}\) that intersect inside an axis-aligned query range \({Q}\) . We present data structures of size \(O(n\cdot {{\mathrm{polylog\,}}}n)\) and with query time \(O((k+1)\cdot {{\mathrm{polylog\,}}}n)\) time, where k is the number of reported pairs, for two classes of objects in \({\mathbb R}^2\) : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in \({\mathbb R}^3\) , we present a data structure of size \(O(n\sqrt{n}\cdot {{\mathrm{polylog\,}}}n)\) and query time \(O((\sqrt{n}+k)\cdot {{\mathrm{polylog\,}}}n)\) . When the objects and query are fat, we obtain \(O((k+1)\cdot {{\mathrm{polylog\,}}}n)\) query time using \(O(n\cdot {{\mathrm{polylog\,}}}n)\) storage. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0384-3 Issue No:Vol. 80, No. 11 (2018)

Authors:Takuro Fukunaga Pages: 3270 - 3292 Abstract: Abstract Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating set ((k, m)-CDS) is defined as a subset S of V such that each node in \(V{\setminus }S\) has at least m neighbors in S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. In this paper, we consider the case in which \(k \le m\) , and we present a simple \(O(k5^k)\) -approximation algorithm for the unweighted (k, m)-CDS problem, and a primal-dual \(O(k^2 \log k)\) -approximation algorithm for the weighted (k, m)-CDS problem. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0385-2 Issue No:Vol. 80, No. 11 (2018)

Authors:Joan Boyar; Leah Epstein; Lene M. Favrholdt; Kim S. Larsen; Asaf Levin Pages: 3293 - 3315 Abstract: Abstract We study two versions of graph coloring, where the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. For classic vertex coloring, the goal is to minimize the maximum color used, and for the sum coloring problem, the goal is to minimize the sum of colors assigned to all input vertices. In the offline variant, the entire graph is presented at once, and in online problems, one vertex is presented for coloring at each time, and the only information is the identity of its neighbors among previously known vertices. In batched graph coloring, vertices are presented in k batches, for a fixed integer \(k \ge 2\) , such that the vertices of a batch are presented as a set, and must be colored before the vertices of the next batch are presented. This last model is an intermediate model, which bridges between the two extreme scenarios of the online and offline models. We provide several results, including a general result for sum coloring and results for the classic graph coloring problem on restricted graph classes: We show tight bounds for any graph class containing trees as a subclass (forests, bipartite graphs, planar graphs, and perfect graphs, for example), and an interesting result for interval graphs and \(k=2\) , where the value of the (strict and asymptotic) competitive ratio depends on whether the graph is presented with its interval representation or not. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0386-1 Issue No:Vol. 80, No. 11 (2018)

Authors:Boris Aronov; Prosenjit Bose; Erik D. Demaine; Joachim Gudmundsson; John Iacono; Stefan Langerman; Michiel Smid Pages: 3316 - 3334 Abstract: Abstract We consider preprocessing a set S of n points in convex position in the plane into a data structure supporting queries of the following form: given a point q and a directed line \(\ell \) in the plane, report the point of S that is farthest from (or, alternatively, nearest to) the point q among all points to the left of line \(\ell \) . We present two data structures for this problem. The first data structure uses \(O(n^{1+\varepsilon })\) space and preprocessing time, and answers queries in \(O(2^{1/\varepsilon }\log n)\) time, for any \(0< \varepsilon < 1\) . The second data structure uses \(O(n \log ^3 n)\) space and polynomial preprocessing time, and answers queries in \(O(\log n)\) time. These are the first solutions to the problem with \(O(\log n)\) query time and \(o(n^2)\) space. The second data structure uses a new representation of nearest- and farthest-point Voronoi diagrams of points in convex position. This representation supports the insertion of new points in clockwise order using only \(O(\log n)\) amortized pointer changes, in addition to \(O(\log n)\) -time point-location queries, even though every such update may make \(\Theta (n)\) combinatorial changes to the Voronoi diagram. This data structure is the first demonstration that deterministically and incrementally constructed Voronoi diagrams can be maintained in o(n) amortized pointer changes per operation while keeping \(O(\log n)\) -time point-location queries. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0389-y Issue No:Vol. 80, No. 11 (2018)

Authors:Jiawei Qian; Seeun William Umboh; David P. Williamson Pages: 3335 - 3364 Abstract: Abstract In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston (Proceedings of the 29th annual ACM symposium on theory of computing, pp 344–353, 1997) and one for (offline) general network design problems due to Goemans and Williamson (SIAM J Comput 24:296–317, 1995); we give an \(O(\log k)\) -competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints; we give an online \(O(\log k)\) -competitive algorithm for this case as well. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0391-4 Issue No:Vol. 80, No. 11 (2018)

Authors:Raphael Reitzig; Sebastian Wild Pages: 3365 - 3396 Abstract: Abstract Given a set of n sticks of various (not necessarily different) lengths, what is the largest length so that we can cut k equally long pieces of this length from the given set of sticks' We analyze the structure of this problem and show that it essentially reduces to a single call of a selection algorithm; we thus obtain an optimal linear-time algorithm. This algorithm also solves the related envy-free stick-division problem, which Segal-Halevi et al. (ACM Trans Algorithms 13(1):1–32, 2016. ISSN: 15496325. https://doi.org/10.1145/2988232) recently used as their central primitive operation for the first discrete and bounded envy-free cake cutting protocol with a proportionality guarantee when pieces can be put to waste. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0392-3 Issue No:Vol. 80, No. 11 (2018)

Authors:Karl Bringmann; Tobias Friedrich; Anton Krohmer Pages: 3397 - 3427 Abstract: Abstract There are hundreds of online social networks with altogether billions of users. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy—it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an n-vertex graph, our algorithm uses \(n^\varepsilon \) seed nodes (for an arbitrarily small \(\varepsilon \) ) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta (n)\) seed nodes and have runtimes of order \(n^{1+\Omega (1)}\) . Additionally, the applicability of our algorithm is studied experimentally on different networks. PubDate: 2018-11-01 DOI: 10.1007/s00453-017-0395-0 Issue No:Vol. 80, No. 11 (2018)

Authors:Aline Saettler; Eduardo Laber; Ferdinando Cicalese Pages: 3431 - 3436 Abstract: Abstract This erratum fixes a technical problem in the paper published in Algorithmica, Volume 79, Number 3, November 2017, pp. 886–908. Theorem 1 of this paper gives upper bounds on both worst testing cost and expected testing cost of the decision tree built by Algorithm 1. PubDate: 2018-11-01 DOI: 10.1007/s00453-018-0423-8 Issue No:Vol. 80, No. 11 (2018)

Abstract: Abstract The authors regret the following error in their article “A connection between sports and matroids: How many teams can we beat'” (Algorithmica, doi: 10.1007/s00453-016-0256-2), considering the computational complexity of the problem MinStanding(S). In Theorem 3 of our paper [4], we erroneously claimed a \(\mathsf {W}[1]\) -hardness result to hold even for the case where the undirected version of the input graph is claw-free. In fact, we can only prove the theorem for \(K_{1,4}\) -free graphs, so the property claw-free should have been replaced by the property \(K_{1,4}\) -free. PubDate: 2018-11-01 DOI: 10.1007/s00453-016-0256-2) considering the computational complexity of the problem