____  __
  ______     _______


Evangelos Kranakis, Carleton U., Canada (co-chair)
Gonzalo Navarro, University of Chile, Chile (co-chair)

[Top] [Home] [All LATIN Chairs]

  Program Committee

Argimiro Arratia Quesada, U. Valladolid, Spain
A. Amir, Johns Hopkins/Bar-Ilan, USA/Israel
D. Achlioptas, U.California, USA
A. Apostolico (+), U. Padova/Georgia Tech, Italy/USA
D. Belazzougui, U. Helsinki, Finland
M. Bender, Stonybrook U., USA
E. Chávez, CICESE, Mexico
C. Kaklamanis, U. Patras, Greece
J. Díaz, UPC Barcelona, Spain
M. Farach-Colton, Rutgers U., USA
C. Fernandes, U. São Paulo, Brazil
E. Feuerstein, U. Buenos Aires, Argentina
F. Fomin, U. Bergen, Norway
L. Gasieniec, U. Liverpool, England
J. von zur Gathen, U. Bonn, Germany
K. Georgiou, U. Waterloo, Canada
R. Grossi, U. Pisa, Italy
G. F. Italiano, U. Rome, Italy
M. Kiwi, U. Chile, Chile
E. Kranakis, D. Krizanc, Wesleyan U., USA
G. Kucherov, CNRS/LIGM, France
G. M. Landau, Haifa and NYU-Poly, Israel/USA
L. Moura, U. Ottawa, Canada
J. I. Munro, U. Waterloo, Canada
L. Narayanan, Concordia U., Canada
G. Navarro, Y. Nekrich, U. Waterloo, Canada
J. Opatrny, Concordia U., Canada
D. Panario, Carleton U., Canada
P. Perez-Lantero, U. Valparaíso, Chile
S. Rajsbaum, UNAM, Mexico
R. Raman, I. Rapaport, U. Chile, Chile
J. Rolim, U. Geneva, Switzerland
N. Santoro, Carleton U., Canada
G. Salazar, UASLP, Mexico
S. Suri, U. California, USA
D. M. Thilikos, CNRS/LIRMM and U. Athens, France/Greece
J. Urrutia, UNAM, Mexico
P. Widmayer, ETH Zurich, Switzerland

[Top] [Home] [All LATIN PCs]

  Organizing Committee

E. Chávez, CICESE, Mexico
D. Flores (publicity co-chair), UNAM, Mexico
D. Imbs (publicity co-chair), U. Bremen, Germany
M. Alcántara (web master), UNAM, Mexico
A. Ballinas (web master), UNAM, Mexico

[Top] [Home] [All LATIN Org. Committees]

  Invited Speakers

Jin Akiyama (Tokyo University of Science), Reversible Figures and Solids

An example of reversible (or hinge inside-out transformable) figures is Dudeney's Haberdasher's puzzle in which an equilateral triangle is dissected into four pieces, hinged like a chain, and then is transformed into a square by rotating the hinged pieces. Furthermore, the entire boundary of each figure goes into the inside of the other figure and becomes the dissection lines of the figure. Many intriguing results on reversibilities of figures have been found in the preceding research, but most of them are results on polygons. We generalize those results to general connected figures. It is shown that two nets obtained by cutting the surface of an arbitrary convex polyhedron along non-interesting dissection trees are reversible. Moreover, we generalize reversibility for 2D-figures to one for 3D-solids.

Joint work with Jin Akiyama (Tokyo University of Science).

Allan Borodin (University of Toronto), Simplicity Is in Vogue (again)

Throughout history there has been an appreciation of the importance of simplicity in the arts and sciences. In the context of algorithm design, and in particular in apprxoximation algorithms and algorithmic game theory, the importance of simplicity is currently very much in vogue. I will present some examples of the current interest in the design of “simple algorithms”. And what is a simple algorithm? Is it just “you'll know it when you see it”, or can we benefit from some precise models in various contexts?

José Correa (Universidad de Chile), Subgame Perfect Equilibrium: Computation and Efficiency
The concept of Subgame Perfect Equilibrium (SPE) naturally arises in games which are played sequentially. In a simultaneous game the natural solution concept is that of a Nash equilibrium in which no players has an incentive to unilaterally deviate from her current strategy. However, if the game is played sequentially, i.e., there is a prescribed order in which the players make their moves, an SPE is a situation in which all players anticipate the full strategy of all other players contingent on the decisions of previous players. Although most research in algorithmic game theory has been devoted to understand properties of Nash equilibria including its computation and the so-called price of anarchy in recent years there has been an interest in understanding the computational properties of SPE and its corresponding efficiency measure, the sequential price of anarchy.

In this talk we will review some of these recent results putting particular emphasis on a very basic game, namely that of atomic selfish routing in a network. In particular we will discuss some hardness results such as the PSPACE-completeness of computing an SPE and its NP-hardness even when the number of players fixed to two. We will also see that for interesting classes of games SPE avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. However, for the atomic network routing games with linear latencies, where the price of anarchy has long been known to be equal to \(5/2\), we prove that the sequential price of arachy is not bounded by any constant and can be as large as \(\Omega(\sqrt{n})\), with \(n\) being the number of players.

Alan Frieze (Carnegie Mellon University), Buying Stuff Online
Suppose there is a collection \(x_1, x_2, \ldots, x_N\) of independent uniform \([0, 1]\) random variables, and a hypergraph \(F\) of target structures on the vertex set \(\{1, \ldots, N\}\). We would like to buy a target structure at small cost, but we do not know all the costs \(x_i\) ahead of time. Instead, we inspect the random variables \(x_i\) one at a time, and after each inspection, choose to either keep the vertex \(i\) at cost \(x_i\), or reject vertex \(i\) forever.

In the present paper, we consider the case where \(\{1, \ldots, N\}\) is the edge-set of some graph, and the target structures are the spanning trees of a graph; the spanning arborescences of a digraph; the Hamilton cycles of a graph; the prefect matchings of a graph; the paths between a fixed pair of vertices; or the cliques of some fixed size.

Joint work with Wesley Pegden (CMU).

Héctor García-Molina (Stanford University), Data Crowdsourcing: Is It for Real?
Crowdsourcing refers to performing a task using human workers that solve sub-problems that arise in the task. In this talk I will give an overview of crowdsourcing, focusing on how crowdsourcing can help traditional data processing and analysis tasks. I will also give a brief overview of some of the crowdsourcing research we have done at the Stanford University InfoLab.

[Top] [Home] [All LATIN Inv. Speakers]


Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov and Saket Saurabh, A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion. [Bibtex]

Hee-Kap Ahn, Helmut Alt, Maike Buchin, Eunjin Oh, Ludmila Scharf and Carola Wenk, A Middle Curve Based on Discrete Fréchet Distance. [Bibtex]

Kamal Al-Bawani, Matthias Englert and Matthias Westermann, Comparison-Based FIFO Buffer Management in QoS Switches. [Bibtex]

Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli and Richard Stotz, Scheduling on Power-Heterogeneous Processors. [Bibtex]

Amihood Amir, Mika Amit, Gad M. Landau and Dina Sokol, Period Recovery over the Hamming and Edit Distances. [Bibtex]

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior and Michele Scquizzato, Chasing Convex Bodies and Functions. [Bibtex]

N. R. Aravind, R. B. Sandeep and Naveen Sivadasan, Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems. [Bibtex]

Pradeesha Ashok, Sudeshna Kolay and Saket Saurabh, Parameterized Complexity of Red Blue Set Cover for Lines. [Bibtex]

Sang Won Bae, Chan-Su Shin and Antoine Vigneron, Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons. [Bibtex]

Evangelos Bampas and David Ilcinkas, On Mobile Agent Verifiable Problems. [Bibtex]

Indranil Banerjee and Dana Richards, Computing Maximal Layers of Points in Ef(n). [Bibtex]

Michael A. Bekos, Michael Kaufmann and Robert Krug, On the Total Number of Bends for Planar Octilinear Drawings. [Bibtex]

Djamal Belazzougui, Travis Gagie, Veli Mäkinen, Marco Previtali and Simon J. Puglisi, Bidirectional Variable-Order de Bruijn Graphs. [Bibtex]

Fernando Benavides and Sergio Rajsbaum, The Read/Write Protocol Complex Is Collapsible. [Bibtex]

Michael A. Bender, Rezaul Chowdhury, Alexander Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon and Shikha Singh, The I/O Complexity of Computing Prime Tables. [Bibtex]

Olivier Bodini, Matthieu Dien, Xavier Fontaine, Antoine Genitrini and Hsien-Kuei Hwang, Increasing Diamonds. [Bibtex]

Katerina Böhmová, Yann Disser, Matús Mihalák and Rastislav Srámek, Scheduling Transfers of Resources over Time: Towards Car-Sharing with Flexible Drop-Offs. [Bibtex]

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos and Georgios Stamoulis, A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs. [Bibtex]

Prosenjit Bose, Darryl Hill and Michiel H. M. Smid, Improved Spanning Ratio for Low Degree Plane Spanners. [Bibtex]

Iffat Chowdhury and Matt Gibson, Constructing Consistent Digital Line Segments. [Bibtex]

Marek Chrobak and Kevin P. Costello, Faster Information Gathering in Ad-Hoc Radio Tree Networks. [Bibtex]

Mercè Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell and Carlos Seara, Stabbing Circles for Sets of Segments in the Plane. [Bibtex]

Manfred Cochefert, Jean-François Couturier, Serge Gaspers and Dieter Kratsch, Faster Algorithms to Enumerate Hypergraph Transversals. [Bibtex]

Alessio Conte, Roberto Grossi, Andrea Marino and Romeo Rizzi, Listing Acyclic Orientations of Graphs with Single and Multiple Sources. [Bibtex]

Maxime Crochemore, Gabriele Fici, Robert Mercas and Solon P. Pissis, Linear-Time Sequence Comparison Using Minimal Absent Words & Applications. [Bibtex]

Patrick Baxter Dragon, Oscar I. Hernandez and Aaron Williams, The Grandmama de Bruijn Sequence for Binary Strings. [Bibtex]

Pål Grønås Drange, Markus S. Dregi and R. B. Sandeep, Compressing Bounded Degree Graphs. [Bibtex]

Amalia Duch, Gustavo Lau and Conrado Martínez, Random Partial Match in Quad-\(K\)-d Trees. [Bibtex]

David Eppstein and Daniel S. Hirschberg, From Discrepancy to Majority. [Bibtex]

David Eppstein, Philipp Kindermann, Stephen G. Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides and Stephen K. Wismath, On the Planar Split Thickness of Graphs. [Bibtex]

Hossein Esfandiari and Guy Kortsarz, A Bounded-Risk Mechanism for the Kidney Exchange Game. [Bibtex]

Martin Farach-Colton and Meng-Tsung Tsai, Tight Approximations of Degeneracy in Large Graphs. [Bibtex]

Cristina G. Fernandes, Samuel P. de Paula and Lehilton L. C. Pedrosa, Improved Approximation Algorithms for Capacitated Fault-Tolerant \(k\)-Center. [Bibtex]

Martin Fink, John Hershberger, Subhash Suri and Kevin Verbeek, Bundled Crossings in Embedded Graphs. [Bibtex]

Carsten Fischer and Heiko Röglin, Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering. [Bibtex]

Johannes Fischer, Tomohiro I. and Dominik Köppl, Deterministic Sparse Suffix Sorting on Rewritable Texts. [Bibtex]

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers, Minimizing the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi Orderings. [Bibtex]

Samuele Giraudo and Stéphane Vialette, Unshuffling Permutations. [Bibtex]

Nicholas J. A. Harvey and Keyulu Xu, Generating Random Spanning Trees via Fast Matrix Multiplication. [Bibtex]

Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth, Routing in Unit Disk Graphs. [Bibtex]

Kolja Knauer and Bartosz Walczak, Graph Drawings with One Bend and Few Slopes. [Bibtex]

Michal Kotrbcík, Rastislav Královic and Sebastian Ordyniak, Edge-Editing to a Dense and a Sparse Graph Class. [Bibtex]

Nirman Kumar and Subhash Suri, Containment and Evasion in Stochastic Point Data. [Bibtex]

Moses Ganardi, Danny Hucke, Markus Lohrey and Eric Noeth, Tree Compression Using String Grammars. [Bibtex]

Victor Marsault and Jacques Sakarovitch, Trees and Languages with Periodic Signature. [Bibtex]

Syed Mohammad Meesum and Saket Saurabh, Rank Reduction of Directed Graphs by Vertex and Edge Deletions. [Bibtex]

Matthias Mnich, Heiko Röglin and Clemens Rösner, New Deterministic Algorithms for Solving Parity Games. [Bibtex]

Eunjin Oh, Sang Won Bae and Hee-Kap Ahn, Computing a Geodesic Two-Center of Points in a Simple Polygon. [Bibtex]

Alice Paul, Matthias Poloczek and David P. Williamson, Simple Approximation Algorithms for Balanced MAX 2SAT. [Bibtex]

Ashutosh Rai, M. S. Ramanujan and Saket Saurabh, A Parameterized Algorithm for Mixed-Cut. [Bibtex]

Saket Saurabh and Meirav Zehavi, \((k, n-k)\)-Max-Cut: An \(O^*(2p)\)-Time Algorithm and a Polynomial Kernel. [Bibtex]

Andreas Wiese, Independent Set of Convex Polygons: From \(n^\epsilon\) to \(1+\epsilon\) via Shrinking. [Bibtex]

[Top] [Home] [All LATIN Papers]


Centro de Investigación Científica y de Educación Superior de Ensenada (CICESE)

[Top] [Home] [All LATIN Sponsors]



The conference was held in Ensenada, Mexico, at the Centro de Investigación Científica y de Educación Superior de Ensenada (CICESE) the largest SEP/CONACyT research center in Mexico.

Eensenada is a coastal city in Mexico, the third-largest in Baja California. Lying 125 kilometres (78 mi) south of San Diego on the Baja California Peninsula, it is locally referred to as La Cenicienta del Pacífico (The Cinderella of the Pacific).

[Top] [Home] [All LATIN Locations]


[Top] [Home] [All LATIN Photos]


No. of submissions 131
No. of accepted papers 52
% of accepted papers 39.7%
Total No. of authors 175
Avg. No. of authors per paper 3.37
No. of countries represented 26
No. of papers according to how many authors work in Latin-America
    At least one 3(5.8%)
    All 2(3.8%)

Statistics by Country of Author's Affiliation


7.0(4.0%)2.00(3.8%)South Korea
2.0(1.1%)0.53(1.0%)Czech Republic
1.0(0.6%)0.33(0.6%)Saudi Arabia

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.

Statistics by Region of Author's Affiliation


50.0(28.6%)14.67(28.2%)USA & Canada
19.5(11.1%)6.08(11.7%)Australia & Asia
6.0(3.4%)1.83(3.5%)Middle East

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Algeria Belazzougui, Djamal;

Australia & Asia

Taiwan Hwang, Hsien-Kuei;
South Korea Ahn, Hee-Kap; Oh, Eunjin; Shin, Chan-Su; Won Bae, Sang;
Australia Gaspers, Serge;
India Aravind, N. R.; Ashok, Pradeesha; Kolay, Sudeshna; Mohammad Meesum, Syed; Rai, Ashutosh; Sandeep, R. B.; Saurabh, Saket; Sivadasan, Naveen;


Italy Conte, Alessio; Fici, Gabriele; Grossi, Roberto; Liotta, Giuseppe; Marino, Andrea; Previtali, Marco; Rizzi, Romeo;
Finland Gagie, Travis; Mäkinen, Veli; Puglisi, Simon J.;
Spain Claverol, Mercè; Duch, Amalia; Lau, Gustavo; Mart{í}nez, Conrado; Seara, Carlos;
Norway Agrawal, Akanksha; Dregi, Markus S.; Grønås Drange, Pål; Lokshtanov, Daniel; Saurabh, Saket;
Netherlands Mihalák, Matús; Verbeek, Kevin;
Poland Walczak, Bartosz;
Slovakia Královic, Rastislav;
Germany Al-Bawani, Kamal; Albers, Susanne; Alt, Helmut; Antoniadis, Antonios; Bekos, Michael A.; Buchin, Maike; Disser, Yann; Fischer, Carsten; Fischer, Johannes; Ganardi, Moses; Hucke, Danny; I., Tomohiro; Kaufmann, Michael; Kindermann, Philipp; Köppl, Dominik; Krug, Robert; Lohrey, Markus; Mercas, Robert; Mnich, Matthias; Mulzer, Wolfgang; Noeth, Eric; Röglin, Heiko; Rösner, Clemens; Scharf, Ludmila; Schewior, Kevin; Seiferth, Paul; Stotz, Richard; Westermann, Matthias; Wiese, Andreas;
Switzerland Böhmová, Katerina; Khramtcova, Elena; Mihalák, Matús; Papadopoulou, Evanthia; Srámek, Rastislav;
UK Crochemore, Maxime; Englert, Matthias; Mercas, Robert; Pissis, Solon P.;
France Bampas, Evangelos; Bampis, Evripidis; Bodini, Olivier; Cochefert, Manfred; Couturier, Jean-François; Dien, Matthieu; Escoffier, Bruno; Fontaine, Xavier; Fraigniaud, Pierre; Genitrini, Antoine; Giraudo, Samuele; Ilcinkas, David; Knauer, Kolja; Kratsch, Dieter; Letsios, Dimitrios; Lucarelli, Giorgio; Maignan, Aude; Marsault, Victor; Paschos, Vangelis Th.; Sakarovitch, Jacques; Simon, Bertrand; Stamoulis, Georgios; Travers, Corentin; Vialette, Stéphane;
Hungary Bonnet, Édouard;
Czech Republic Kotrbcík, Michal; Saumell, Maria;
Austria Ordyniak, Sebastian; Ramanujan, M. S.;


Mexico Benavides, Fernando; Rajsbaum, Sergio;
Brazil de Paula, Samuel P.; Fernandes, Cristina G.; Pedrosa, Lehilton L. C.;
Colombia Benavides, Fernando;

Middle East

Israel Amir, Amihood; Amit, Mika; Kaplan, Haim; Landau, Gad M.; Roditty, Liam; Zehavi, Meirav;
Saudi Arabia Vigneron, Antoine;

USA & Canada

USA Amir, Amihood; Banerjee, Indranil; Barcelo, Neal; Baxter Dragon, Patrick; Bender, Michael A.; Chowdhury, Iffat; Chowdhury, Rezaul; Chrobak, Marek; Conway, Alexander; Costello, Kevin P.; Eppstein, David; Esfandiari, Hossein; Farach-Colton, Martin; Fink, Martin; Ganapathi, Pramod; Gibson, Matt; Hernandez, Oscar I.; Hershberger, John; Hirschberg, Daniel S.; Johnson, Rob; Kobourov, Stephen G.; Kortsarz, Guy; Kumar, Nirman; Landau, Gad M.; McCauley, Samuel; Nugent, Michael; Paul, Alice; Poloczek, Matthias; Pruhs, Kirk; Richards, Dana; Scquizzato, Michele; Singh, Shikha; Sokol, Dina; Suri, Subhash; Tsai, Meng-Tsung; Wenk, Carola; Williams, Aaron; Williamson, David P.;
Canada Bose, Prosenjit; Harvey, Nicholas J. A.; Hill, Darryl; Lubiw, Anna; Mondal, Debajyoti; Smid, Michiel H. M.; Vosoughpour, Hamideh; Whitesides, Sue; Wismath, Stephen K.; Xu, Keyulu;

[Top] [Home] [All LATIN Statistics]