LATIN 2018: Theoretical Informatics

1. Front Matter

   Pages I-XVII

   PDF

2. The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness

   • Alexandre Abreu, Luís Cunha, Tharso Fernandes, Celina de Figueiredo, Luis Kowada, Franklin Marquezino et al.

   Pages 1-13

3. Approximate Correlation Clustering Using Same-Cluster Queries

   • Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal

   Pages 14-27

4. Finding Tight Hamilton Cycles in Random Hypergraphs Faster

   • Peter Allen, Christoph Koch, Olaf Parczyk, Yury Person

   Pages 28-36

5. Walking Through Waypoints

   • Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Stefan Schmid

   Pages 37-51

6. A Collection of Lower Bounds for Online Matching on the Line

   • Antonios Antoniadis, Carsten Fischer, Andreas Tönnis

   Pages 52-65

7. On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths

   • Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, Ignasi Sau, Ana Silva

   Pages 66-79

8. Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets

   • Sandip Banerjee, Sujoy Bhore, Rajesh Chitnis

   Pages 80-93

9. A Polynomial Sized Kernel for Tracking Paths Problem

   • Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh

   Pages 94-107

10. Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees

    • Bahareh Banyassady, Luis Barba, Wolfgang Mulzer

    Pages 108-119

11. Approximate Nearest Neighbor Search for \(\ell _p\)-Spaces \((2<p<\infty )\) via Embeddings

    • Yair Bartal, Lee-Ad Gottlieb

    Pages 120-133

12. The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model

    • Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

    Pages 134-145

13. Partitioning Orthogonal Histograms into Rectangular Boxes

    • Therese Biedl, Martin Derka, Veronika Irvine, Anna Lubiw, Debajyoti Mondal, Alexi Turcotte

    Pages 146-160

14. Compact Self-Stabilizing Leader Election for General Networks

    • Lélia Blin, Sébastien Tixeuil

    Pages 161-173

15. Random Walks with Multiple Step Lengths

    • Lucas Boczkowski, Brieuc Guinard, Amos Korman, Zvi Lotker, Marc Renault

    Pages 174-186

16. Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set

    • Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, Sudeshna Kolay

    Pages 187-200

17. A Tight Bound for Shortest Augmenting Paths on Trees

    • Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz

    Pages 201-216

18. Approximation Algorithms for Replenishment Problems with Fixed Turnover Times

    • Thomas Bosman, Martijn van Ee, Yang Jiao, Alberto Marchetti-Spaccamela, R. Ravi, Leen Stougie

    Pages 217-230

19. Maximum Box Problem on Stochastic Points

    • Luis Evaristo Caraballo, Pablo Pérez-Lantero, Carlos Seara, Inmaculada Ventura

    Pages 231-244

20. The Online Set Aggregation Problem

    • Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, José Verschae

    Pages 245-259

This book constitutes the proceedings of the 13th Latin American Symposium on Theoretical Informatics, LATIN 2018, held in Buenos Aires, Argentina, in April 2018. The 63 papers presented in this volume were carefully reviewed and selected from 161 submissions. The Symposium is devoted to different areas in theoretical computer science, including, but not limited to: algorithms (approximation, online, randomized, algorithmic game theory, etc.), analytic combinatorics and analysis of algorithms, automata theory and formal languages, coding theory and data compression, combinatorial algorithms, combinatorial optimization, combinatorics and graph theory, complexity theory, computational algebra, computational biology, computational geometry, computational number theory, cryptology, databases and information retrieval, data structures, formal methods and security, Internet and the web, parallel and distributed computing, pattern matching, programming language theory, and random structures.

• ad hoc networks
• approximation algorithms
• artificial intelligence
• coloring
• graph theory
• graphic methods
• planar graph
• polynomial-time algorithms
• probability
• random processes
• telecommunication networks
• wireless telecommunication systems
• computational geometry
• algorithmic game theory
• pattern matching
• algorithm analysis and problem complexity
• data structures

• Stony Brook University, Stony Brook, USA

  Michael A. Bender

• Rutgers University, New Brunswick, USA

  Martín Farach-Colton

• Pace University, New York, USA

  Miguel A. Mosteiro

Policies and ethics