LATIN 2012: Theoretical Informatics

Table of Contents

1. Frontmatter

2. A Generalization of the Convex Kakeya Problem

   Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama, Antoine Vigneron

   Abstract

   We consider the following geometric alignment problem: Given a set of line segments in the plane, find a convex region of smallest area that contains a translate of each input segment. This can be seen as a generalization of Kakeya’s problem of finding a convex region of smallest area such that a needle can be turned through 360 degrees within this region. Our main result is an optimal Θ(n logn)-time algorithm for our geometric alignment problem, when the input is a set of n line segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then the optimum placement is when the midpoints of the segments coincide. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of any rotated copy of G.

3. Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines

   Eric Angel, Evripidis Bampis, Vincent Chau

   Abstract

   Power management aims in reducing the energy consumed by computer systems while maintaining a good level of performance. One of the mechanisms used to save energy is the shut-down mechanism which puts the system into a sleep state when it is idle. No energy is consumed in this state, but a fixed amount of energy is required for a transition from the sleep state to the active state which is equal to L times the energy required for the execution of a unit-time task. In this paper, we focus on the off-line version of this problem where a set of unit-time tasks with release dates and deadlines have to be scheduled in order to minimize the overall consumed energy during the idle periods of the schedule. Here we focus on the case where the tasks have agreeable deadlines. For the single processor case, an O(n ³) algorithm has been proposed in [7] for unit-time tasks and arbitrary L. We improve this result by introducing a new O(n ²) polynomial-time algorithm for tasks with arbitrary processing times and arbitrary L. For the multiprocessor case we also improve the complexity from O(n ³ m ²) [7] to O(n ² m) in the case of unit-time tasks and unit L.

4. Bichromatic 2-Center of Pairs of Points

   Esther M. Arkin, José Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph S. B. Mitchell, Belén Palop, Pablo Pérez-Lantero, Maria Saumell, Rodrigo I. Silveira

   Abstract

   We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points, assign to each point a color (“red” or “blue”) so that each pair’s points are assigned different colors and a function of the radii of the minimum enclosing balls of the red points and the blue points, respectively, is optimized. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii. For each case, minmax and minsum, we consider distances measured in the L ₂ and in the L _∞ metrics. Our problems are motivated by a facility location problem in transportation system design, in which we are given origin/destination pairs of points for desired travel, and our goal is to locate an optimal road/flight segment in order to minimize the travel to/from the endpoints of the segment.

5. Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs

   Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

   Abstract

   Given a finite group G by its multiplication table, we give a deterministic polynomial-time construction of a directed O(log|G|) degree Cayley expander for G. Our construction exploits the connection between rapid mixing random walks and spectral expansion. Our main group-theoretic tool is Erdős-Rényi sequences. We give a similar construction of O(log|G|) degree undirected Cayley expanders for G, which is an alternative proof of Wigderson and Xiao’s derandomization [WX08] of the Alon-Roichman randomized construction.

6. A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem

   Rafael da Ponte Barbosa, Yoshiko Wakabayashi

   Abstract

   We study a one-dimensional sensor cover problem, known as the Restricted Strip Cover (RSC) problem, defined as follows. We are given an interval U of the real line, and a set of n sensors, each of which covers some subinterval of U and is powered with a battery of limited duration. The RSC problem consists in assigning a starting time to each sensor so that the whole interval U is covered for as long as possible. We assume that when a sensor is turned on (at its starting time) it remains on through the duration of its battery.

   Buchsbaum, Efrat, Jain, Venkatasubramanian and Yi showed that RSC is NP-hard and designed an O(loglogn)-approximation algorithm. More recently, Gibson and Varadarajan presented a greedy-like algorithm which they proved to have approximation ratio at most 5. We prove that the approximation ratio of this algorithm is 4, and exhibit an instance showing that this ratio is tight. We also show an integer programming formulation for this problem and present some computational results obtained with the implementation of this approach. For the same set of instances, we compute the quality of the solution found by the approximation algorithm.

7. On the Advice Complexity of the Knapsack Problem

   Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Peter Rossmanith

   Abstract

   We study the advice complexity and the random bit complexity of the online knapsack problem: Given a knapsack of unit capacity, and n items that arrive in successive time steps, an online algorithm has to decide for every item whether it gets packed into the knapsack or not. The goal is to maximize the value of the items in the knapsack without exceeding its capacity. In the model of advice complexity of online problems, one asks how many bits of advice about the unknown parts of the input are both necessary and sufficient to achieve a specific competitive ratio. It is well-known that even the unweighted online knapsack problem does not admit any competitive deterministic online algorithm. We show that a single bit of advice helps a deterministic algorithm to become 2-competitive, but that \(\ensuremath{\mathrm{\Omega}\mathopen{}\left(\log n\right)} \) advice bits are necessary to further improve the deterministic competitive ratio. This is the first time that such a phase transition for the number of advice bits has been observed for any problem. We also show that, surprisingly, instead of an advice bit, a single random bit allows for a competitive ratio of 2, and any further amount of randomness does not improve this. Moreover, we prove that, in a resource augmentation model, i.e., when allowing a little overpacking of the knapsack, a constant number of advice bits suffices to achieve a near-optimal competitive ratio. We also study the weighted version of the problem proving that, with \(\ensuremath{\mathcal{O}\hspace*{-0.4pt}\mathopen{}\left(\log n\right)} \) bits of advice, we can get arbitrarily close to an optimal solution and, using asymptotically fewer bits, we are not competitive.

8. Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems

   Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

   Abstract

   The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I′ resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT in order to solve Π in I’, either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. We use this setting in order to study weighted versions of several representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. The main problems studied are max independent set, max k-colorable subgraph and max split subgraph under vertex insertions and deletions.

9. On Plane Constrained Bounded-Degree Spanners

   Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot

   Abstract

   Let P be a set of points in the plane and S a set of non-crossing line segments with endpoints in P. The visibility graph of P with respect to S, denoted \(\mathord{\it Vis}(P,S)\), has vertex set P and an edge for each pair of vertices u,v in P for which no line segment of S properly intersects uv. We show that the constrained half-θ ₆-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of \(\mathord{\it Vis}(P,S)\). We then show how to construct a plane 6-spanner of \(\mathord{\it Vis}(P,S)\) with maximum degree 6 + c, where c is the maximum number of segments adjacent to a vertex.

10. Space-Efficient Approximation Scheme for Circular Earth Mover Distance

    Joshua Brody, Hongyu Liang, Xiaoming Sun

    Abstract

    The Earth Mover Distance (EMD) between point sets A and B is the minimum cost of a bipartite matching between A and B. EMD is an important measure for estimating similarities between objects with quantifiable features and has important applications in several areas including computer vision. The streaming complexity of approximating EMD between point sets in a two-dimensional discretized grid is an important open problem proposed in [8,9].

    We study the problem of approximating EMD in the streaming model, when points lie on a discretized circle. Computing the EMD in this setting has applications to computer vision [13] and can be seen as a special case of computing EMD on a discretized grid. We achieve a (1 ±ε) approximation for EMD in \(\tilde O(\varepsilon^{-3})\) space, for every 0 < ε < 1. To our knowledge, this is the first streaming algorithm for a natural and widely applied EMD model that matches the space bound asked in [9].

11. Density Classification on Infinite Lattices and Trees

    Ana Bušić, Nazim Fatès, Jean Mairesse, Irène Marcovici

    Abstract

    Consider an infinite graph with nodes initially labeled by independent Bernoulli random variables of parameter p. We want to find a (probabilistic or deterministic) cellular automaton or a finite-range interacting particle system that decides if p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0’s if p < 1/2, and only 1’s if p > 1/2. We present solutions to that problem on ℤ ^d , for any d ≥ 2, and on the regular infinite trees. For ℤ, we propose some candidates that we back up with numerical simulations.

12. Coloring Planar Homothets and Three-Dimensional Hypergraphs

    Jean Cardinal, Matias Korman

    Abstract

    We prove that every finite set of homothetic copies of a given compact and convex body in the plane can be colored with four colors so that any point covered by at least two copies is covered by two copies with distinct colors. This generalizes a previous result from Smorodinsky (SIAM J. Disc. Math. 2007). Then we show that for any k ≥ 2, every three-dimensional hypergraph can be colored with 6(k − 1) colors so that every hyperedge e contains min { |e|,k } vertices with mutually distinct colors. This refines a previous result from Aloupis et al. (Disc. & Comp. Geom. 2009). As corollaries, we obtain constant factor improvements for conflict-free coloring, k-strong conflict-free coloring, and choosability. Proofs of the upper bounds are constructive and yield simple, polynomial-time algorithms.

13. An Equivariance Theorem with Applications to Renaming

    Armando Castañeda, Maurice Herlihy, Sergio Rajsbaum

    Abstract

    In the renaming problem, each process in a distributed system is issued a unique name from a large name space, and the processes must coordinate with one another to choose unique names from a much smaller name space.

    We show that lower bounds on the solvability of renaming in an asynchronous distributed system can be formulated as a purely topological question about the existence of an equivariant chain map from a “topological disk” to a “topological annulus”. Proving the non-existence of such a map implies the non-existence of a distributed renaming algorithm in several related models of computation.

14. Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks

    Armando Castañeda, Damien Imbs, Sergio Rajsbaum, Michel Raynal

    Abstract

    In the wait-free shared memory model substantial attention has been devoted to understanding the relative power of sub-consensus tasks. Two important sub-consensus families of tasks have been identified: k-set agreement and M-renaming. When 2 ≤ k ≤ n − 1 and n ≤ M ≤ 2n − 2, these tasks are more powerful than read/write registers, but not strong enough to solve consensus for two processes.

    This paper studies the power of renaming with respect to set agreement. It shows that, in a system of n processes, n-renaming is strictly stronger than (n − 1)-set agreement, but not stronger than (n − 2)-set agreement. Furthermore, (n + 1)-renaming cannot solve even (n − 1)-set agreement. As a consequence, there are cases where set agreement and renaming are incomparable when looking at their power to implement each other.

15. Pseudorandomness of a Random Kronecker Sequence

    Eda Cesaratto, Brigitte Vallée

    Abstract

    We study two randomness measures for the celebrated Kronecker sequence \({\cal S}(\alpha)\) formed by the fractional parts of the multiples of a real α. The first measure is the well-known discrepancy, whereas the other one, the Arnold measure, is less popular. Both describe the behaviour of the truncated sequence \({\cal S}_T(\alpha)\) formed with the first T terms, for T → ∞. We perform a probabilistic study of the pseudorandomness of the sequence \({\cal S}(\alpha)\) (discrepancy and Arnold measure), and we give estimates of their mean values in two probabilistic settings : the input α may be either a random real or a random rational. The results exhibit strong similarities between the real and rational cases; they also show the influence of the number T of truncated terms, via its relation to the continued fraction expansion of α.

16. Revisiting the Cache Miss Analysis of Multithreaded Algorithms

    Richard Cole, Vijaya Ramachandran

    Abstract

    This paper revisits the cache miss analysis of algorithms when scheduled using randomized work stealing (RWS) in a parallel environment where processors have private caches. We focus on the effect of task migration on cache miss costs, and in particular, the costs of accessing “hidden” data typically stored on execution stacks (such as the return location for a recursive call).

    Prior analyses, with the exception of [1], do not account for such costs, and it is not clear how to extend them to account for these costs. By means of a new analysis, we show that for a variety of basic algorithms these task migration costs are no larger than the costs for the remainder of the computation, and thereby recover existing bounds. We also analyze a number of algorithms implicitly analyzed by [1], namely Scans (including Prefix Sums and Matrix Transposition), Matrix Multiply (the depth n in-place algorithm, the standard 8-way divide and conquer algorithm, and Strassen’s algorithm), I-GEP, finding a longest common subsequence, FFT, the SPMS sorting algorithm, list ranking and graph connected components; we obtain sharper bounds in many cases.

    While this paper focusses on the RWS scheduler, the bounds we obtain are a function of the number of steals, and thus would apply to any scheduler given bounds on the number of steals it induces.

17. Parameterized Complexity of MaxSat above Average

    Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman, Saket Saurabh

    Abstract

    In MaxSat, we are given a CNF formula F with n variables and m clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let r ₁,…, r _m be the number of literals in the clauses of F. Then \({\rm asat}(F)=\sum_{i=1}^m (1-2^{-r_i})\) is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least asat(F) clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least asat(F) + k clauses, where k is the (nonnegative) parameter. We prove that MaxSat-AA is para-NP-complete and thus, MaxSat-AA is not fixed-parameter tractable unless P=NP. This is in sharp contrast to the similar problem MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (FSTTCS 2011).

    In fact, we consider a more refined version of MaxSat-AA, Max- r(n)-Sat-AA, where r _j  ≤ r(n) for each j. Alon et al. (SODA 2010) proved that if r = r(n) is a constant, then Max- r -Sat-AA is fixed-parameter tractable. We prove that Max- r(n)-Sat-AA is para-NP-complete for r(n) = ⌈logn⌉. We also prove that assuming the exponential time hypothesis, Max- r(n)-Sat-AA is not fixed-parameter tractable already for any r(n) ≥ loglogn + φ(n), where φ(n) is any unbounded strictly increasing function. This lower bound on r(n) cannot be decreased much further as we prove that Max- r(n)-Sat-AA is fixed-parameter tractable for any r(n) ≤ loglogn − logloglogn − φ(n), where φ(n) is any unbounded strictly increasing function. The proof uses some results on MaxLin2-AA.

18. Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n

    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

    Abstract

    The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z ₁ ,Z ₂ , asks whether it is possible to find disjoint sets A ₁ ,A ₂ , such that Z ₁ ⊆ A ₁ , Z ₂ ⊆ A ₂ and A ₁ ,A ₂ induce connected subgraphs. While the naive algorithm runs in O(2 ⁿ n ^O(1)) time, solutions with complexity of form O((2 − ε) ⁿ ) have been found only for special graph classes [15, 19]. In this paper we present an O(1.933 ⁿ ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 ⁿ barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.