Chair


Evangelos Kranakis,
Carleton U., Canada (cochair)
Gonzalo Navarro,
University of Chile, Chile (cochair)


[Top]
[Home]
[All LATIN Chairs]


Program Committee


Argimiro Arratia Quesada, U. Valladolid, Spain
A. Amir, Johns Hopkins/BarIlan, 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. FarachColton, 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 NYUPoly, 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. PerezLantero, 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 cochair),
UNAM, Mexico
D. Imbs (publicity cochair),
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 insideout 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 noninteresting dissection trees are reversible. Moreover, we
generalize reversibility for 2Dfigures to one for 3Dsolids.
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 socalled 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 PSPACEcompleteness of computing an SPE
and its NPhardness 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
edgeset 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íaMolina
(Stanford University), Data Crowdsourcing: Is It for Real?
Crowdsourcing refers to performing a task using human workers that
solve subproblems 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]


Papers


Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov and Saket Saurabh, A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion. [Bibtex]
HeeKap Ahn, Helmut Alt, Maike Buchin, Eunjin Oh, Ludmila Scharf and Carola Wenk, A Middle Curve Based on Discrete Fréchet Distance. [Bibtex]
Kamal AlBawani, Matthias Englert and Matthias Westermann, ComparisonBased FIFO Buffer Management in QoS Switches. [Bibtex]
Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli and Richard Stotz, Scheduling on PowerHeterogeneous 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 NPcompleteness of Hfree Edge Modification Problems. [Bibtex]
Pradeesha Ashok, Sudeshna Kolay and Saket Saurabh, Parameterized Complexity of Red Blue Set Cover for Lines. [Bibtex]
Sang Won Bae, ChanSu Shin and Antoine Vigneron, Tight Bounds for BeaconBased 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 VariableOrder 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 FarachColton, 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 HsienKuei Hwang, Increasing Diamonds. [Bibtex]
Katerina Böhmová, Yann Disser, Matús Mihalák and Rastislav Srámek, Scheduling Transfers of Resources over Time: Towards CarSharing with Flexible DropOffs. [Bibtex]
Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos and Georgios Stamoulis, A 0.821Ratio Purely Combinatorial Algorithm for Maximum kvertex 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 AdHoc 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, JeanFranç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, LinearTime 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 BoundedRisk Mechanism for the Kidney Exchange Game. [Bibtex]
Martin FarachColton and MengTsung 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 FaultTolerant \(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 NextFit 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 FaultTolerant Distributed Decision Using WellQuasi 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, EdgeEditing 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 HeeKap Ahn, Computing a Geodesic TwoCenter 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 MixedCut. [Bibtex]
Saket Saurabh and Meirav Zehavi, \((k, nk)\)MaxCut: 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]


Sponsors



[Top]
[Home]
[All LATIN Sponsors]


Location



[Top]
[Home]
[All LATIN Locations]


Photos



[Top]
[Home]
[All LATIN Photos]


Statistics


General: 
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 LatinAmerica 
At least one  3  (5.8%) 
All  2  (3.8%) 
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
Africa
Australia & Asia
Taiwan 
Hwang, HsienKuei;

South Korea 
Ahn, HeeKap;
Oh, Eunjin;
Shin, ChanSu;
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;

Europe
Finland 
Gagie, Travis;
Mäkinen, Veli;
Puglisi, Simon J.;

UK 
Crochemore, Maxime;
Englert, Matthias;
Mercas, Robert;
Pissis, Solon P.;

Norway 
Agrawal, Akanksha;
Dregi, Markus S.;
Grønås Drange, Pål;
Lokshtanov, Daniel;
Saurabh, Saket;

Hungary 
Bonnet, Édouard;

France 
Bampas, Evangelos;
Bampis, Evripidis;
Bodini, Olivier;
Cochefert, Manfred;
Couturier, JeanFranç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;

Poland 
Walczak, Bartosz;

Austria 
Ordyniak, Sebastian;
Ramanujan, M. S.;

Czech Republic 
Kotrbcík, Michal;
Saumell, Maria;

Italy 
Conte, Alessio;
Fici, Gabriele;
Grossi, Roberto;
Liotta, Giuseppe;
Marino, Andrea;
Previtali, Marco;
Rizzi, Romeo;

Slovakia 
Královic, Rastislav;

Germany 
AlBawani, 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;

Netherlands 
Mihalák, Matús;
Verbeek, Kevin;

Spain 
Claverol, Mercè;
Duch, Amalia;
Lau, Gustavo;
Mart{í}nez, Conrado;
Seara, Carlos;

Switzerland 
Böhmová, Katerina;
Khramtcova, Elena;
Mihalák, Matús;
Papadopoulou, Evanthia;
Srámek, Rastislav;

LatinAmerica
Middle East
USA & Canada
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;

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;
FarachColton, 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, MengTsung;
Wenk, Carola;
Williams, Aaron;
Williamson, David P.;



[Top]
[Home]
[All LATIN Statistics]

