ESA WABI IPEC WAOA ALGOSENSORS ATMOS MASSIVE
ALGO 2012
Ljubljana, September 9-14, 2012
University of Ljubljana
Dear guests,
on behalf of the ALGO 2012 Organization Committee we warmly wel- come you to Slovenia and Ljubljana. We also welcome you on behalf of the University of Ljubljana and its Faculty of Computer and Infor- mation Science.
After a great organization of ALGO 2011 by Max Planck Institute for Informatics it was not easy to step in their shoes. We most sincerely hope though you will enjoy the venue of the Grand Hotel Union and charming downtown of Ljubljana and that they will not only foster your scientific fruitfulness, but also attract you to come back to our city and perhaps also visit our University. We wish you a stay as pleasant as possible.
The number of participating conferences this year grew by one as MASSIVE (Workshop on Massive Data Al- gorithmics) joined ALGO.
Consequently, ALGO now consists of the following fine conferences:
• ESA - European Symposium on Algorithms
• WABI - Workshop on Algorithms for Bioinformatics
• ALGOSENSORS - International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities
• IPEC - International Symposium on Parameterized and Exact Computation
• WAOA - Workshop on Approximation and
Online Algorithms
• ATMOS - Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
• MASSIVE - Workshop on Massive Data Algorithmics
As the fil rouge interconnecting 187 talks and two tutorials are eight plenary talks given by distinguished speakers who give the conference additional value and charm if we may say so. Furthermore, we man- aged to attract Videolectures portal to record their talks and publish them and make them even more memorable. We want thank jointly to speakers, who agreed to be recorded, and also to Videolectures to
further promote our fine conference.
We would like to express our gratitude to all the chairs of Program Committees of the conferences who were timely providing us with all the key information necessary to organize the ALGO 2012 meeting. The cooperation with them was most efficient and enjoy- able.
We further want to thank all sponsors who sup- ported ALGO 2012 and PRO FIT who helped us to run the event smoothly. Thanx also to authors of CoSeSy system we picked from last year to better synchronize up to five parallel sessions.
We also want express our gratitude to University of Ljubljana and its Faculty of Computer and Information Science and numerous their employees who always stood
by and helped us. Thank you also to all others we
might forget to mention here.
Finally, it is our great pleasure to extend our thanks to the colleagues who made this conference possible with their work. First, we are grateful to all the members of the Organization Committe: Gaš per Fele-Ž orž , Matevž Jekovec, Jurij Mihelič, Uroš Čibej and Andrej Tolič have been hard-working and most helpful conference-organizers in the past year or so. We further thank Tomaž Dobravec and Mitja Bezenš ek, and all our students, who kindly volunteered to help during the conference.
At last, but most definitely not least, thank you, dear guests, to come to ALGO 2012!
Sincerely,
Andrej Brodnik and Borut Robič co-chairs of the Organization Committee ALGO 2012
Dean's thoughts
The University of Ljubljana was established in 1919 in Ljubljana, the capital city of Slovenia. As the central educational and research insti- tution for the Republic of Slovenia, with its orientation towards growth and quality has established itself as one of the most promi- nent Universities in Europe and the World. By the standards of ARWU (Academic Ranking of World Universities) it is being placed among the first 500 six years in a row, it is also being ranked 106 on the Webometrics on the global scale and 29 place in Europe. From the school year 2007/2008 all the study programs are in accordance with the Bologna declaration. University of Ljubljana is considered a big University, as it is attended by some 63000 undergraduate and postgraduate students and employs around 5000 teachers. With its 3 academies and 23 faculties its goal is to achieve the highest standards in fields of science and art. It is exchanging its achievements in the field of science and arts with other universities and research facilities and in doing so contributing to the global wealth of knowledge. It is involved in the economy and service industry in the public and private sectors, the government, local community and other institutions of civil society. Thereby facilitates the use of its research and educa- tional achievements and contributes to social development.
Faculty of Computer and Information Science is an independent member of the University of Ljubljana since the 1st of January 1996.
The study of computer science has been conducted on the University of Ljubljana since 1973 as part of a study course on the faculty of Electrical Engineering, and in the year 1982 it became an indepen- dent study program.
It is Slovenia’ s leading institution in the field of Computer Sciences and Information Technologies and is highly ranked in comparison to other faculties around the world. Since the first study program in
1973 the faculty has constantly evolved. Introducing new multidisci- plinary study programs, expanding our expertise with new teachers, laboratories, cutting edge research equipment and many projects on which we collaborate with the economic sector and other universities and research institutions around the world.
Since 2012 onward specific courses in Master’ s programs and the whole of Doctoral programs are being conducted in the English lan- guage, because we feel that our study programs are interesting not only for Slovenian students, but internationally as well. With these in mind we would like to attract foreign researchers and professors in or- der to achieve a higher scientific level.
The main goal of the Faculty of Computer and Information Science is the education of computer experts of different profiles. The forms of education differ in scope, difficulty, method of implementation and number of participants. In addition to regular education the faculty is conducting supplementary education for computer experts as well as experts from other scientific fields needing additional knowledge in the field of computer science.
We take a personal approach in the education of young investigators during postgraduate programs under the tutelage of university profes- sors who introduce them to scientific work.
From the Faculty of Computer and Information Science until now graduated 2896 undergraduate students, 371 Masters of philosophy and 124 Doctors of philosophy.
At the present time the Faculty of Computer and Information Science is accommodating 1381 undergraduate and 131 postgraduate stu- dents. The Faculty employs around 95 teachers and assistants, 58 re- searchers and 28 people in administration and technical support. The teaching personnel are working within 20 laboratories.
The interest in the study of computer and information sciences on our faculty is outstanding, since every year we get 600 candidates in-
terested in enrolling, so every year our faculty is at full capacity with 180 students. The Faculty of Computer and Information Science of- fers eight different first-cycle and second-cycle programs and three third-cycle programs. A double degree program is being prepared in cooperation with the Graz University of Technology, Austria.
The Faculty of Computer and Information Science takes extra care of different fields of computer science. More over it is getting notable results in the fields of Data Mining, Computer Vision, Artificial Intelli- gence, Cloud Computing and Algorithms and Data Structures.
This year the Faculty of Computer and Information Science in coop- eration with the Faculty of Chemistry and Chemical Technologies, with the help of European Union’ s regional development fund, begun to construct a new facility building. This long standing project is equally important to Slovenia’ s regional development and the Euro- pean Union as a whole. The University of Ljubljana gained funding from the European Union, for one of Europe’ s biggest investments in the field of educational-research infrastructure for the period of 2007- 2013.
We are pleased that the Faculty of Computer and Information Sci- ence of the University of Ljubljana, has been given the honour to host this year's ALGO conference. Algorithmics is a field of study that the Faculty is trying to nurture more ambitiously.
Nikolaj Zimic
University of Ljubljana Dean of the
Faculty of Computer and Information Science
General Information
Ljubljana airport – city connections
Recommended way of getting from the airport to Ljubljana city is us- ing GRH chaffeur services. They offer transports according to the air- craft arrivals/departures 24/7 and they will drive you all the way to your hotel. Trip takes around 30 minutes. One way prices range from 12€ per person for a Shuttle bus (max. waiting time 1h) to 40€ per car for a private transfer (1-3 persons, no waiting time). Register your transfer at http://grh.si and select “ ALGO conference” . In case of a trouble contact GRH directly on +386 41 376 964.
Public buses are also operating every hour on working days and every two hours on weekends. Bus takes around 55 minutes and costs 4.10€ . It arrives to Ljubljana central bus station, which is 10 minutes of walking time from the conference place. For information on sched- ules check http://ap-ljubljana.si/eng. Airport is called “ Letališ če Brnik” in Slovenian and the central station is called “ Ljubljana AV- TOBUSNA POSTAJA” .
Public transportation in Ljubljana
ALGO 2012 is held in Grand Hotel Union Executive. Basically there are two ways to travel around Ljubljana – using LPP buses or Bi- cikeLJ bicycles. ALGO 2012 attendees have an unlimited access to use of LPP buses on local bus lines by showing their ALGO 2012 badge upon entering the bus. Bus lines map can be found on page 18 in the tourist guide. Attendees staying in Hotel Plaza (quadrant J7 on the map) should take a bus number 2 from the bus stop “ Nove Jarš e” to the bus stop “ Konzorcij/Poš ta” . It starts every 10-20 min- utes and the ride takes approximately 30 minutes. BicikeLJ bicycles will cost you 1€ for a weekly usage. Information regarding bicycle ac-
cess points and the registration is at http://en.bicikelj.si.
Information desk, registration
Information/registration desk is located on the right side when enter- ing the Grand Hotel Union Executive building. The information/regis- tration desk is open 16:00-20:00 on Sunday and 8:00-20:00 on other days except on Tuesday when it closes at 16:00 due to excursion.
Moreover, our students and other staff is around and is more than happy to answer your questions.
Internet access
There is a freely accessible WLAN available at the hotel. Connect to GHUGUESTS access point. To enable web access, open a web browser and enter the guest password GHUINTERNET (all capital letter).
Technical support
ALGO 2012 employs technical staff in each lecture hall. They wear a badge with a red rectangle and an “ Organizer” or “ Staff” label. Do not hesitate to contact any of them, if you encounter any technical problems.
Session organization
ALGO 2012 features seven conferences and workshops in up to five parallel sessions. In order to allow attendees to easily switch sessions between talks, we synchronize all lecture halls with a Conference Ses- sion Syncronizer (CoSeSy). Each of the five lecture halls are equipped with a big screen that indicates the remaining time for each talk. All slots are 25 minutes long and speakers are requested to observe the time: 20 minutes for the talk (green color+orange at the end of the
talk), 2 minutes for questions (red) and 3 minutes for breaks between talks for changing the speaker and set up equipment (blue). CoSeSy timers can be accessed by anyone by visiting the following URLs ranging from Monday to Friday:
http://cosesy.mpi-inf.mpg.de/index.php?id=algo2012mo http://cosesy.mpi-inf.mpg.de/index.php?id=algo2012tu http://cosesy.mpi-inf.mpg.de/index.php?id=algo2012we http://cosesy.mpi-inf.mpg.de/index.php?id=algo2012th http://cosesy.mpi-inf.mpg.de/index.php?id=algo2012fr
Each speaker will have a laser pointing device, presentation computer with a display and a video projector available. Presentation computers will have Microsoft Office 2010 installed, LibreOffice 3.6.1 and Acro- bat PDF viewer. All speakers should report to the session chair before the session starts.
The main responsibility of the session chair is to keep the session run- ning on schedule as indicated by the provided timer. Session chairs should arrive early and invite speakers to test their own equipment before the session starts. Most importantly, please ensure that speak- ers start and stop on time. If talk ends early, we would kindly ask you to wait until the break between talks ends and the timer turns green again. In case of any technical issues, there will be member of staff available in each lecture room.
Catering
Lunches are organized in hotel's restaurant. Coffee breaks and snacks are in Blue room. Each lunch consists of 3 rounds (starter, main dish, dessert) and also covers a glass of juice. All ALGO attendees are re- quired to show their badge when entering the restaurant. Persons, who at registration entered special requirements should mention this to the waiter.
Social events – Welcome reception, excursion to Postojna cave and the conference dinner
Welcome reception with the welcome drink will be organised in Gar- den Hall on Sunday at 18:00.
On Tuesday afternoon we will take an excursion to Postojna cave, the second longest cave system in the country – since about a month ago; before it was the longest one ;-) After the excursion there will be a conference dinner with live music (Trio KRANJC, http://triokranjc.si). Rough schedule:
17:00 – Bus leaving Grand Hotel Union Executive 17:45 – Arrival to Postojna
18:00 – Visit to Postojna cave
19:30 – Conference dinner at “ Jamski dvorec” restaurant 22:00 – Departure back to Ljubljana
Organizing Committee
ALGO 2012 was organized by the University of Ljubljana, Faculty of Computer and Information Science.
Organizing committee:
Andrej Brodnik Borut Robič
Gaš per Fele-Ž orž Matevž Jekovec
Jurij Mihelič Uroš Čibej
Andrej Tolič
Plenary talks
Monday On Big Data Algorithmics
Yossi Matias, Google and Tel-Aviv University, USA/Israel ESA
Tuesday Algorithms for Genome Rearrangement by Double Cut and Join Jens Stoye, University of Bielefeld, Germany
WABI
Wednesday Open Problems in Throughput Scheduling
Jiří Sgall, Charles University in Prague, Czech republic ESA
Thursday
Randomized techniques for parameterized algorithms Dániel Marx, Hungarian Academy of Sciences, Hungary IPEC
Algorithm Engineering of Timetable Information
Matthias Müller-Hannemann, University of Halle-Wittenberg, Germany ATMOS
Friday
Geometric Computing over Uncertain Data
Subhash Suri, University of California, Santa Barbara, USA ALGOSENSORS
The path taken for k-path
Andreas Björklund, Lund University, Sweden IPEC
The Primal-Dual approach for Online Algorithms
Nikhil Bansal, Eindhoven University of Technology, Netherlands WAOA
Conferences
ESA
The ESA symposia are devoted to fostering and disseminating the re- sults of high quality research on the design and evaluation of algo- rithms and data structures. The forum seeks original algorithmic con- tributions for problems with relevant theoretical and/or practical ap- plications and aims at bringing together researchers in the computer science and operations research communities. Papers were solicited in all areas of algorithmic research, both theoretical and experimental, and were evaluated by two Program Committees (PC). The PC of Track A (Design and Analysis) selected contributions with a strong emphasis on the theoretical analysis of algorithms. The PC of Track B (Engineering and Applications) evaluated papers reporting on the results of experimental evaluations and on algorithm engineering con- tributions for interesting applications.
The conference received 285 submissions from 40 countries. Each submission was reviewed by at least three program committee mem- bers, and carefully evaluated on quality, originality, and relevance to the conference. Overall, the program committees wrote more than 900 reviews with the help of more than 500 trusted external referees, who also participated in an extensive electronic discussion that led the committees of the two tracks to select 69 papers (56 out of 231 in Track A and 13 out of 54 in Track B), leading to an acceptance rate of about 24%. In addition to the accepted contributions, the Symposium featured two distinguished plenary lectures by Yossi Ma- tias (Google Israel and Tel Aviv University) and Jiří Sgall (Charles University, Prague).
The European Association for Theoretical Computer Science (EATCS) sponsored a best paper award and a best student paper
award. The former award was shared by two papers: one by Clément Maria and Jean-Daniel Boissonnat for their contribution on “ The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes” , and the other by Sebastian Wild and Markus E. Nebel for their contribution titled “ Average Case Analysis of Java 7's Dual Pivot Quicksort” . The best student paper prize was awarded to Mar- tin Groß, Jan-Philipp W. Kappmeier, Daniel R. Schmidt and Melanie Schmidt for their contribution titled “ Approximating Earliest Arrival Flows in Arbitrary Networks” . Our warmest congratulations to them for these achievements.
We would like to thank all the authors who responded to the call for papers, the invited speakers, the members of the program commit- tees, as well as the external referees and the organizing committee members. We also gratefully acknowledge the developers and main- tainers of the EasyChair conference management system, which pro- vided invaluable support throughout the selection process and the preparation of these proceedings. We hope that the readers will enjoy the papers published in this volume, sparking their intellectual curios- ity and providing inspiration for their work.
Leah Epstein and Paolo Ferragina ESA 2012 Program Chairs Program commitee Track A:
Matthias Englert, University of Warwick, United Kingdom Leah Epstein (chair), University of Haifa, Israel
Gregory Gutin, University of London, United Kingdom Pinar Heggernes, University of Bergen, Norway Martin Hoefer, RWTH Aachen University, Germany Jochen Könemann, University of Waterloo, Canada Petr Kolman, Charles University, Czech Republic
Kim Skak Larsen, University of Southern Denmark, Denmark Asaf Levin, The Technion, Israel
Alejandro López-Ortiz, University of Waterloo, Canada Krzysztof Onak, Carnegie Mellon University, USA Dror Rawitz, Tel-Aviv University, Israel
Günter Rote, Freie Universität Berlin, Germany Andreas Schulz, MIT, USA
Ola Svensson, EPFL Lausanne, Switzerland Marc Uetz, University of Twente, The Netherlands Carola Wenk, University of Texas at San Antonio, USA Peter Widmayer, ETH Zurich, Switzerland
Christian Wulff-Nilsen, University of Southern Denmark, Denmark Raphael Yuster, University of Haifa, Israel
Program committee Track B:
Susanne Albers, Humboldt University, Berlin, Germany Alexandr Andoni, Microsoft Research, USA
Ioannis Z. Emiris, National Kapodistrian University of Athens, Greece Paolo Ferragina (chair), University of Pisa, Italy
Irene Finocchi, Sapienza University of Rome, Italy
Johannes Fischer, Karlsruhe Institute of Technology, Germany Michael T. Goodrich, University of California, Irvine, USA
Herman Haverkort, Eindhoven University of Technology, Netherlands Vahab Mirrokni, Google Research, USA
Gonzalo Navarro, University of Chile, Chile
Rina Panigrahy, Microsoft Research Silicon Valley, USA Rajeev Raman, University of Leicester, United Kingdom Jens Stoye, Bielefeld University, Germany
Oren Weimann, University of Haifa, Israel
Ke Yi, Hong Kong University of Science and Technology, China
WABI
The Workshop on Algorithms in Bioinformatics (WABI) focuses on al- gorithmic advances in bioinformatics, computational biology, and sys- tems biology with a particular emphasis on discrete algorithms and machine-learning methods that address important problems in molec- ular biology.
For this 12th WABI, 35 papers were selected for presentation from a total of 92 submissions. The 35 papers this volume include algorithms for a variety of biological problems including phylogeny, DNA and RNA sequencing and analysis, protein structure, and others.
WABI 2012 also features a keynote address “ Genome Rearrangement by Double Cut and Join” by Jens Stoye, Universitat Bielefeld.
The papers were selected by the Program Committee below, which was chaired by Ben Raphael (Brown University, USA) and Jijun Tang (University of South Carolina, USA).
Ben Raphael and Jijun Tang WABI 2012 Program Chairs Program committee:
Tatsuya Akutsu, Kyoto University, Japan
Max Alekseyev, University of South Carolina, USA Mathieu Blanchette, McGill University, Canada
Guillaume Blin, Université Paris-Est LIGM UMR CNRS 8049, France Paola Bonizzoni, Universita di Milano-Bicocca, Italy
Daniel Brown, University of Waterloo, Canada
Philipp Bucher, Swiss Institute for Experimental Cancer Research Sebastian Bocker, Friedrich Schiller University Jena, Germany Lenore Cowen, Tufts University, USA
Minghua Deng, Peking University, China
Pufeng Du, Tianjin University, China
Nadia El-Mabrouk, University of Montreal, Canada Guillaume Fertin, LINA, University of Nantes, France Liliana Florea, Johns Hopkins University, USA Anna Gambin, Warsaw University, Poland
Olivier Gascuel, LIRMM, CNRS – Université Montpellier 2, France Katharina Huber, University of East Anglia, UK
Daniel Huson, University of Tübingen, Germany
Carl Kingsford, University of Maryland, College Park, USA Jim Leebens-Mack, University of Georgia, USA
Xinghua Lu, University of Pittsburgh, USA Ion Mandoiu, University of Connecticut, USA Satoru Miyano, University of Tokyo, Japan Bernard Moret, EPFL, Switzerland
Burkhard Morgenstern, Universitat Gottingen, Germany Vincent Moulton, University of East Anglia, UK
Luay Nakhleh, Rice University, USA Macha Nikolski, LaBRI, France
Ron Pinter, Technion – Israel Institute of Technology, Israel Nadia Pisanti, Universita di Pisa, Italy
Mihai Pop, University of Maryland, USA
Teresa Przytycka, National Institutes of Health (NIH), USA Tal Pupko, Tel Aviv University, Israel
Sven Rahmann, University of Duisburg-Essen, Germany Ben Raphael (Co-chair), Brown University, USA
Marie-France Sagot, INRIA and Université de Lyon, France David Sankoff, University of Ottawa, Canada
Thomas Schiex, INRA, France
Russell Schwartz, Carnegie Mellon University, USA Charles Semple, University of Canterbury, New Zealand Roded Sharan, Tel Aviv University, Israel
Jingna Si, Zhejiang University, China Joerg Stelling, ETH Zurich, Switzerland Leen Stougie, VU University, The Netherlands Jens Stoye, Bielefeld University, Germany
Krister Swenson, Université de Montréal / McGill University, Canada Jijun Tang (Co-chair), University of South Carolina, USA
Glenn Tesler, University of California, San Diego, USA Jerzy Tiuryn, Warsaw University, Poland
Li-San Wang, University of Pennsylvania, USA Lusheng Wang, City University of Hong Kong, China
Christopher Workman, Technical University of Denmark, Denmark Feng Yue, University of California San Diego, USA
Alex Zelikovsky, Georgia State University, USA
Louxin Zhang, National University of Singapore, Singapore Meng Zhang, Jilin University, China
Xiuwei Zhang, EPFL, Switzerland
Ziding Zhang, China Agricultural University, China
WABI accepted posters
Orange Bioinformatics: Computational Data Analytics for Biologists
Marko Toplak, Ales Erjavec, Janez Demsar, Gregor Rot, Gad Shaulsky, Tomaz Curk, and Blaz Zupan
Multiple genome comparison based on overlap regions of pairwise local alignments Katharina Jahn, Henner Sudek, and Jens Stoye
NOrMAL: Accurate Nucleosome Positioning using a Modified Gaussian Mixture Model
Anton Polishko, Nadia Ponts, Karine Le Roch, Stefano Lonardi OB-Fold Recognition Combining Sequence and Structural Motifs Martin Macko, Martin Králik, Brońa Brejová, and Tomáš Vina ř Unraveling Overlapping Deletions by Agglomerative Clustering
Roland Wittler, Tobias Marschall, Linda K. Sundermann and Jens Stoye SyntenyFinder: A Synteny Blocks Generation and Genome Comparison Tool Ilya Minkin, Nikolay Vyahhi, and Son Pham
Seed based, reference-less and targeted assembly on eukaryotic scale Tobias Jakobi, Alexander Goesmanny, Jens Stoye, and Alfred Pühler Implementation of Succinct de Bruijn Graphs
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya PIPAx: next generation sequencing data analytics at hand
Gregor Rot, Balaji Santhanam, Marko Toplak, Tomaz Curk, Adam Kuspa, Gad Shaulsky and Blaz Zupan
Path-Extend: An Approach for Repeat Resolution in de novo Genome Assembly Andrey D. Prjibelski, Tatiana Krivosheeva, Anton Bankevich, Sergey Nurk, Son Pham, and Pavel A. Pevzner
Predicting cell’ s differentiation staging
Lan Ž agar, Francesca Mulas, Aleš Erjavec, Riccardo Bellazzi, and Blaž Zupan WABI poster session is held in Blue room from Monday till Wednesday.
IPEC
The 7th International Symposium on Parameterized and Exact Com- putation (IPEC 2012) covers research in all aspects of parameterized and exact algorithms and complexity. IPEC is an international sympo- sium series that covers research on all aspects of parameterized and exact algorithms and complexity.
Papers of IPWC present original research in the area, including but not limited to: new techniques for the design and analysis of parame- terized and exact algorithms, fixed-parameter tractability results, pa- rameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, and implementation issues of parameterized and exact algorithms. In particular, studies on parame- terized and exact computations for real-world applications and algo- rithmic engineering are especially encouraged.
The workshop series started in 2004 in Bergen (Norway) as a biennial event, and in 2008 became an annual event. The first four workshops in the series used the five letter acronym IWPEC (which was bulky and hard to pronounce), whereas from the fifth workshop onwards the catchy four letter acronym IPEC has been used. Over the years IPEC has become very visible, and it has grown into one of the main events for the algorithmics and complexity community.
Dimitrios M. Thilikos and Gerhard Woeginger IPEC 2012 Program Chairs
Program committee:
Jianer Chen, Texas A&M University, College Station, USA Marek Cygan, University of Warsaw, Poland
Henning Fernau, University of Trier, Germany Fedor V. Fomin, University of Bergen, Norway
Martin Grohe, Humboldt University of Berlin, Germany Daniel Kral, Charles University, Prague, Czech republic
Stefan Kratsch, Max Planck Institute for Inf., Saarbrücken, Germany Mikko Koivisto, Helsinki Institute for Information Technology, Finland Igor Razgon, University of Leicester, UK
Saket Saurabh, Institute of Mathematical Sciences, Chennai, India Dimitrios M. Thilikos, National Kapodistrian Univ. of Athens, Greece Erik Jan van Leeuwen, Sapienza University of Rome, Italy
Magnus Wahlstrom, Max Planck Inst. for Inf., Saarbrücken, Germany Gerhard J. Woeginger, Eindhoven Institute of Technology,Netherlands Keynote speakers:
Andreas Bjorklund, Lund University, Sweden
Daniel Marx, Hungarian Academy of Sciences, Budapest, Hungary Tutorial speakers:
Michal Pilipczuk, University of Bergen, Norway
Saket Saurabh, Institute of Mathematical Sciences, Chennai, India
ALGOSENSORS
The ALGOSENSORS event series aims at reinforcing the foundations and algorithmic aspects of all types of Wireless Networks such as Sensor Networks, Ad Hoc Networks, and Mobile Networks. In particu- lar, ALGOSENSORS focuses on abstract models, complexity-theoretic results and lower-bounds as well as the design and analysis of algo- rithms for wireless sensor networks.
Contributions come from all areas where the interplay between com- plexity and communication takes place. In particular from: distributed computing, high-speed networks, interconnection networks, mobile computing, optical computing, parallel computing, sensor networks, wireless networks, and related areas.
This year, 24 submissions were received, of which 11 were accepted as regular papers and 2 accepted as short papers.
Keynote speakers are Subhash Suri, UCSB, and Thomas Kesselheim, TU Aachen.
Amotz Bar-Noy and Magnús M. Halldórsson ALGOSENSORS 2012 Program Chairs Program committee:
Nikhil Bansal, Eindhoven Institute of Technology, Netherlands Amotz Bar-Noy (Chair Track A), City University of New York, USA Prithwish Basu, BBN Technologies, USA
Shlomi Dolev, Ben Gurion University, Israel Leah Epstein, University of Haifa, Israel Thomas Erlebach, University of Leicester, UK Guy Even, Tel Aviv University, Israel
Sándor Fekete, Braunschweig University of Technology, Germany Pierre Fraigniaud, CNRS and University Paris Diderot, France
Jie Gao, SUNY Stony Brook, USA
Ramesh Govindan, University of South California, USA
Magnús M. Halldórsson (Chair Track B), Reykjavik University, Iceland Samir Khuller, University of Maryland, USA
Danny Krizanc, Wesleyan University, USA Fabian Kuhn, University of Lugano, Switzerland Pekka Orponen, Aalto University, Finland
Marina Papatriantafilou, Chalmers University of Technology, Sweden Sriram Pemmaraju, University of Iowa, USA
Yvonne Anne Pignolet, ABB Research Laboratory, Switzerland Geppino Pucci, Universitá di Padova, Italy
Dror Rawitz, Tel Aviv University, Israel
Christian Scheideler, Universität Paderborn, Germany
Stefan Schmid, Technische Universität Berlin (TUB), Germany Mani Srivastava, UCLA, USA
Jukka Suomela, University of Helsinki, Finland Subhash Suri, UCSB, USA
Takeshi Tokuyama, Tohoku University, Japan Amy Y. Wang, Tsinghua University, China
WAOA
Algorithms have become a fundamental tool in several fields outside of Computer Science, and in several applications algorithms have to cope with computationally hard problems and problems in which the input is gradually disclosed over time.
The workshop focuses on the design and analysis of approximation and online algorithms. It also covers experimental methods used to design and analyze efficient approximation and online algorithms.
Papers were solicited in all research areas related to approximation and online algorithms including, but not limited to: algorithmic game theory, algorithmic trading, coloring and partitioning, competitive analysis, computational advertising, computational finance, cuts and connectivity, geometric problems, graph algorithms, inapproximability results, mechanism design, natural algorithms, network design, pack- ing and covering, paradigms for the design and analysis of approxima- tion and online algorithms, parameterized complexity, real-world appli- cations, scheduling problems.
In response to the call for papers, we received 60 submissions. One submission was subsequently withdrawn, and the Program Committee selected 22 papers among the remaining 59 submissions.
The keynote speaker for our workshop will be Nikhil Bansal from the Eindhoven University of Technology.
Thomas Erlebach and Guiseppe Persiano WAOA 2012 Program Chairs
Program Committee:
Evripidis Bampis, Université Pierre et Marie Curie, Paris, France Cristina Bazgan, Université Paris Dauphine, France
Wolfgang Bein, University of Nevada, Las Vegas, USA Marek Chrobak, University of California, Riverside, USA Andrea Clementi, University of Rome “ Tor Vergata” , Italy Thomas Erlebach, University of Leicester (co-chair), Stanley Fung, University of Leicester, UK
Martin Hoefer, RWTH Aachen, Germany Klaus Jansen, University of Kiel, Germany
Christos Kaklamanis, University of Patras & CTI, Greece
Nicole Megow, Max Planck Institute for Inf., Saarbrücken, Germany Seffi Naor, Technion Haifa, Israel
Zeev Nutov, The Open University of Israel, Israel Giuseppe Persiano, Università di Salerno (co-chair), Italy Kirk Pruhs, University of Pittsburgh, USA
Jiří Sgall, Charles University, Prague, Czech Republic Roberto Solis-Oba, University of Western Ontario, Canada
Rob van Stee, Max Planck Institute for Inf., Saarbrücken, Germany Andreas Wiese, Sapienza University of Rome, Italy
Paul Wollan, Sapienza University of Rome, Italy
ATMOS
Transportation networks give rise to very complex and large-scale net- work optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer sci- ence, and operations research. Applicable tools and concepts include those from graph and network algorithms, combinatorial optimization, approximation and online algorithms, stochastic and robust optimiza- tion. Since 2000, the series of ATMOS workshops brings together re- searchers and practitioners who are interested in all aspects of algo- rithmic methods and models for transportation optimization and pro- vides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transporta- tion.
The 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'12) was held in con- nection with ALGO 2012, hosted by University of Ljubljana, Slovenia, on September 13, 2012. Topics of interest for ATMOS'12 were all optimization problems for passenger and freight transport, including – but not limited to – Infrastructure Planning, Vehicle Scheduling, Crew and Duty Scheduling, Rostering, Routing in Road Networks, Novel Applications of Route Planning Techniques, Demand Forecasting, De- sign of Tariff Systems, Delay Management, Mobile Applications, Hu- manitarian Logistics, Simulation Tools, Line Planning, Timetable Gen- eration, and Routing and Platform Assignment. Of particular interest were: the successful integration of several (sub)problems or planning stages, algorithms operating in an online/realtime or stochastic set- ting, and heuristic approaches (including approximation algorithms) for real-world instances.
In response to the call for papers we received 22 submissions, all of which were reviewed by at least four referees. The submissions were
judged on originality, technical quality, and relevance to the topics of the conference. Based on the reviews, the program committee se- lected the 12 papers which appear in this volume. Together, they quite impressively demonstrate the range of applicability of algorith- mic optimization to transportation problems in a wide sense. In addi- tion, Matthias Müller-Hannemann kindly agreed to complement the program with an invited talk entitled “ Algorithm Engineering of Timetable Information” .
Daniel Delling and Leo Liberti ATMOS 2012 Program Chairs Program committee:
Teodor Gabriel Crainic, Université du Québec and Montréal, Canada Daniel Delling, Microsoft Research Silicon Valley, USA (co-chair) Daniele Frigioni, University of L'Aquila, Italy
Felix König, TomTom, Germany
Gilbert Laporte, HEC Montreal, Canada
Leo Liberti, Ecole Polytechnique, France (co-chair) Marco Lübbecke, RWTH Aachen University, Germany Frédéric Meunier, Ecole des Ponts ParisTech, France Giacomo Nannicini, SUTD, Singapore
Carolina Osorio, MIT, USA Christian Sommer, MIT, USA
Paolo Toth, University of Bologna, Italy
Eduardo Uchoa, Universidade Federal Fluminense, Brazil Roberto Wolfler Calvo, Paris-Nord University, France
MASSIVE
Tremendous advances in our ability to acquire, store and process data, as well as the pervasive use of computers in general, have re- sulted in a spectacular increase in the amount of data being col- lected. This availability of high-quality data has led to major advances in both science and industry. In general, society is becoming increas- ingly data driven, and this trend is likely to continue in the coming years. The increasing number of applications processing massive data means that in general focus on algorithm efficiency is increasing.
However, the large size of the data, and/or the small size of many modern computing devices, also means that issues such as memory hierarchy architecture often play a crucial role in algorithm efficiency.
Thus, the availability of massive data means many new challenges for algorithm designers.
The idea behind the Workshop on Massive Data Algorithmics is to provide a forum for researchers from both academia and industry to present current research within algorithms for massive dataset prob- lems. In the call for papers the scope of the workshop was defined to include both fundamental algorithmic problems involving massive data, as well as algorithms for more specialized problems in, e.g., graphics, databases, statistics and bioinformatics. Topics of interest include, but are not limited to: I/O-efficient algorithms, Cache-oblivi- ous algorithms, Memory hierarchy efficient algorithms, Streaming al- gorithms, Sublinear algorithms, Parallel algorithms for massive data problem, Engineering massive data algorithms.
Earlier iterations of MASSIVE took place in Paris, France; Snowbird, Utah, USA; and in Aarhus, Denmark. The workshop is sponsored by MADALGO.
John Iacono MASSIVE 2012 Program Chair
Program committee:
Alexandr Andoni, Microsoft Silicon Valley, USA Gerth S. Brodal, Aarhus and MADALGO, Denmark Raphaël Clifford, Bristol, UK
Pooya Davoodi, NYU Polytechnic, USA
Martin Farach-Colton, Rutgers and Tokutek, USA Jeremy T. Fineman, Georgetown, USA
Irene Finocchi, Rome, Italy
Michael T. Goodrich, UC Irvine, USA John Iacono (chair), NYU Polytechnic, USA Christian Jensen, Aarhus and MADALGO, Denmark Gad M. Landau, Haifa, Israel
Charles E. Leiserson, MIT, USA
Alejandro López-Ortiz, Waterloo, Canada Yakov Nekrich, University of Chile, Chile
Rasmus Pagh, ITU University of Copenhagen, Denmark Srinivasa Rao Satti, Seoul, Republic of Korea
Ronitt Rubinfeld, MIT and Tel Aviv, USA/Israel Christian Sohler, Dortmund, Germany
Yufei Tao, CUHK/KAIST, China/Republic of Korea Elad Verbin, Aarhus and MADALGO, Denmark Sung-Eui Yoon, KAIST, Republic of Korea Hamid Zarrabi-Zadeh, Sharif, Iran
Organizing committee:
Lars Arge, Aarhus and MADALGO, Denmark
Gerth Stølting Brodal, Aarhus and MADALGO, Denmark John Iacono, NYU Polytechnic, USA
Else Magård, Aarhus and MADALGO, Denmark
Matie Bach Søgaard, Aarhus and MADALGO, Denmark
Schedule
Monday, September 10, 2012
08:45 Welcome by Prof. Radovan Stanislav Pejovnik, rector of University of Ljubljana.
Official opening and opening remarks (ESA, WABI) White Hall
09:00 Plenary talk
On Big Data Algorithmics
Yossi Matias, Google and Tel-Aviv University, USA/Israel Chair: Paolo Ferragina (ESA)
White Hall
10:00 Coffee break
Blue room ESA I – White Hall
Chair: Asaf Levin Approximation algorithms
ESA II – Glass Hall 2+3 Chair: Jens Stoye Graph algorithms
WABI – Glass Hall 1 Chair: Matthias Bernt Phylogenetic Trees 1 10:30 Steiner Forest Orientation
Problems
Marek Cygan, Guy Kortsarz and Zeev Nutov
Better Bounds for Graph Bisection
Daniel Delling and Renato Werneck
Preserving Inversion Phylogeny Reconstruction
Matthias Bernt, Kun-Mao Chao, Jyun-Wei Kao, Martin Middendorf and Eric Tannier 10:55 A 5-approximation for
capacitated facility location Manisha Bansal, Naveen Garg and Neelima Gupta
Hierarchical Hub Labelings for Shortest Paths
Ittai Abraham, Daniel Delling, Andrew Goldberg and Renato Werneck
Fast Phylogenetic Tree Reconstruction Using Locality- Sensitive Hashing
Daniel G. Brown and Jakub Truszkowski
11:20 Approximation of Minimum Cost Homomorphisms
Pavol Hell, Monaldo Mastrolilli, Mayssam Nevisi and Arash Rafiey
I/O-efficient hierarchical diameter approximation Deepak Ajwani, Ulrich Meyer and David Veith
Efficient Computation of Popular Phylogenetic Tree Measures Constantinos Tsirogiannis, Brody Sandel and Dimitris Cheliotis 11:45 Maximum Multicommodity
Flows Over Time without Intermediate Storage
Martin Groß and Martin Skutella
An Experimental Study of Dynamic Dominators
Loukas Georgiadis, Giuseppe F.
Italiano, Luigi Laura and Federico Santaroni
Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs
Rob Gysel, Kristian Stevens and Dan Gusfield
12:10 Lunch
Restaurant
Monday
ESA I – White Hall Chair: Matthias Mnich Graph classes
ESA II – Glass Hall 2+3 Chair: Chien-Chung Huang Network optimization
WABI – Glass Hall 1 Chair: Jens Stoye Genetics 13:30 The Clique Problem in Ray
Intersection Graphs Sergio Cabello, Jean Cardinal and Stefan Langerman
A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk and Piotr Sankowski
SibJoin: A Fast Heuristic for Half-Sibling Reconstruction Daniel G. Brown and Daniel Dexter
13:55 On the Complexity of Metric Dimension
Josep Diaz, Olli Pottonen, Maria Serna and Erik Jan van Leeuwen
Embedding paths into trees: VM placement to minimize congestion
Debojyoti Dutta, Michael Kapralov, Ian Post and Rajendra Shinde
Estimating Population Size via Line Graph Reconstruction Bjarni V. Halldórsson, Dima Blokh and Roded Sharan
14:20 Colouring AT-free graphs Dieter Kratsch and Haiko Muller
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
Shiri Chechik
CLIIQ: Accurate Comparative Detection and Quantification of Expressed Isoforms in a Population
Yen-Yi Lin, Phuong Dao, Faraz Hach, Marzieh Bakhshi, Fan Mo, Anna Lapuk, Colin Collins and S.
Cenk Sahinalp
14:45 Coffee break
Blue room ESA I – White Hall
Chair: Hans Bodlaender Graph algorithms
ESA II – Glass Hall 2+3 Chair: Mark de Berg Distances
WABI – Glass Hall 1 Chair: Daniel G. Brown Networks
15:15 Extending partial representations of function graphs and permutation graphs Pavel Klavik, Jan Kratochvil, Tomasz Krawczyk and Bartosz Walczak
Minimum Average Distance Triangulations
Laszlo Kozma
Sparse Learning Based Linear Coherent Bi-clustering Yi Shi, Xiaoping Liao, Xinhua Zhang, Guohui Lin and Dale Schuurmans
15:40 FPT algorithms for domination in biclique-free graphs Jan Arne Telle and Yngve Villanger
The Stretch Factor of L1- and L∞-Delaunay Triangulations Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and Ljubomir Perkovic
-TRIMAX: Extracting δ
Triclusters and Analysing Coregulation in Time Series Gene Expression Data
Anirban Bhar, Martin Haubrock, Anirban Mukhopadhyay Ujjwal
Monday
Maulik, Sanghamitra Bandyopadhyay and Edgar Wingender
16:05 Parameterized Complexity of Induced H-Matching on Claw- Free Graphs
Danny Hermelin, Matthias Mnich and Erik Jan van Leeuwen
Efficient Communication Protocols for Deciding Edit Distance
Hossein Jowhari
Sign Assignment Problems on Protein Networks
Shay Houri and Roded Sharan
16:30 Coffee break
Blue room ESA I – White Hall
Chair: Danny Hermelin Fixed Parameter Tractability
ESA II – Glass Hall 2+3 Chair: Danny Halperin Computational Geometry
WABI – Glass Hall 1 Chair: Yi Shi
Network, RNA sequence and structure
17:00 Induced Disjoint Paths in Claw- Free Graphs
Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen
Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes
Mark De Berg, Marcel Roeloffzen and Bettina Speckmann
RNA Tree Comparisons via Unrooted Unordered Alignments Nimrod Milo, Shay Zakov, Erez Katzenelson, Eitan Bachmat, Yefim Dinitz and Michal Ziv- Ukelson
17:25 A Polynomial kernel for Proper Interval Vertex Deletion Fedor Fomin, Saket Saurabh and Yngve Villanger
Bottleneck Non-Crossing Matching in the Plane A. Karim Abu-Affash, Paz Carmi, Matthew Katz and Yohai Trabelsi
Tree Decomposition and Parameterized Algorithms for RNA Structure-Sequence Alignment Including Tertiary Interactions and Pseudoknots Philippe Rinaudo, Yann Ponty, Dominique Barth and Alain Denise
17:50 A Fast and Simple
Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization Yasuaki Kobayashi and Hisao Tamaki
Locally Correct Fréchet Matchings
Kevin Buchin, Maike Buchin, Wouter Meulemans and Bettina Speckmann
Reconstructing the Evolution of Molecular Interaction Networks under the DMC and Link Dynamics Models Yun Zhu and Luay Nakhleh
18:30 – 19:30
ESA Business meeting White Hall
WABI business meeting Glass Hall 1
Monday
Tuesday, September 11, 2012 09:00 Plenary talk
Algorithms for Genome Rearrangement by Double Cut and Join Jens Stoye, University of Bielefeld, Germany
Chair: (WABI) White Hall
10:00 Coffee break
Blue room ESA I – White Hall
Chair: Rob van Stee Algorithmic Game Theory 1
ESA II – Glass Hall 2+3 Chair: Alejandro López-Ortiz Networks and Maps
WABI – Glass Hall 1 Chair: Luay Nakhleh Genome Rearrangements 10:30 Resource Buying Games
Tobias Harks and Britta Peis
Time-Dependent Route Planning with Generalized Objective Functions
Gernot Veit Batz and Peter Sanders
A Simplified View of DCJ-Indel Distance
Phillip E.C. Compeau
10:55 Polynomial-time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
Constructing Street Networks from GPS Trajectories Mahmuda Ahmed and Carola Wenk
DCJ-indel Distance with Distinct Operation Costs
Poly H. da Silva, Marília D.V.
Braga, Raphael Machado and Simone Dantas
11:20 Finding Social Optima in Congestion Games with Positive Externalities
Bart De Keijzer and Guido Schaefer
Simplifying Massive Contour Maps
Lars Arge, Lasse Deleuran, Thomas Mølhave, Morten Revsbć k, and Jakob Truelsen
Hidden Breakpoints in Genome Alignments
Birte Kehr, Knut Reinert and Aaron E. Darling
11:45 Solving simple stochastic games with few coin toss positions Rasmus Ibsen-Jensen and Peter Bro Miltersen
Maximum Flow Networks for Stability Analysis of LEGO Structures
Martin Waßmann and Karsten Weicker
Tandem Halving Problems by DCJ
Antoine Thomas, Aïda Ouangraoua and Jean-Stéphane Varré
12:10
Lunch Restaurant
Tuesday
ESA I – White Hall
Chair: Leah Epstein and Paolo Ferragina Best papers session
WABI – Glass Hall 1 Chair: Giovanna Rosone DNA Sequencing and Assembly 1 13:30 Approximating Earliest Arrival Flows in Arbitrary Networks
(student best paper)
Martin Gross, Jan-Philipp W. Kappmeier, Daniel R. Schmidt and Melanie Schmidt
Succinct de Bruijn Graphs Alexander Bowe, Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya
13:55 Average Case Analysis of Java 7's Dual Pivot Quicksort Sebastian Wild and Markus E. Nebel
Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom Filter Rayan Chikhi and Guillaume Rizk 14:20 The Simplex Tree: An Efficient Data Structure for General
Simplicial Complexes
Clément Maria and Jean-Daniel Boissonnat
From de Bruijn Graphs to Rectangle Graphs for Genome Assembly
Nikolay Vyahhi, Alex Pyshkin, Son Pham and Pavel A. Pevzner
14:45 Coffee break
Blue room ESA I – White Hall
Chair: Kirk Pruhs Algorithmic Game Theory 2
ESA II – Glass Hall 2+3 Chair: Pinar Heggernes Networks
WABI – Glass Hall 1 Chair: Kira Vyatkina
DNA Sequencing and Assembly 2 15:15 Optimizing Social Welfare for
Network Bargaining Games in the Face of Unstability, Greed and Spite
T-H. Hubert Chan, Fei Chen and Li Ning
Emanuele Guido Fusco and Andrzej Pelc. Knowledge, Level of Symmetry, and Time of Leader Election
A Probabilistic Approach to Accurate Abundance-Based Binning of Metagenomic Reads Olga Tanaseichuk, James Borneman and Tao Jiang
15:40 Fidaa Abed and Chien-Chung Huang. Preemptive Coordination Mechanisms for Unrelated Machines
Routing Regardless of Network Stability
Bundit Laekhanukit, Adrian Vetta and Gordon Wilfong
FinIS: Improved in silico Finishing Using an Exact Quadratic Programming Formulation Song Gao, Denis Bertrand and Niranjan Nagarajan
16:05 Revenue guarantees in sponsored search auctions
Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos and Maria Kyropoulou
Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph- Freeness
Frank Hellweg and Christian Sohler.
Lightweight LCP Construction for Next-Generation Sequencing Datasets
Markus J. Bauer, Anthony J.
Cox, Giovanna Rosone and Marinella Sciortino
16:30
Excursion to Postojna cave and conference dinner
Tuesday
Wednesday, September 12, 2012 08:45 Opening remarks (IPEC)
White Hall 09:00 Plenary talk
Open Problems in Throughput Scheduling
Jiří Sgall, Charles University in Prague, Czech republic Chair: Leah Epstein (ESA)
White Hall
10:00 Coffee break
Blue room ESA I – White Hall
Chair: Jiří Sgall Scheduling
ESA II – Glass Hall 2+3 Chair: Rajeev Raman Computational Geometry
WABI – Glass Hall 1 Chair: David Fernandez- Baca
Protein Sequence and Structure
IPEC – Red Hall Chair: Fedor V. Fomin IPEC 1
10:30 A Bicriteria Approximation for the Reordering Buffer Problem
Siddharth Barman, Shuchi Chawla and Seeun Umboh
Faster Geometric Algorithms via Dynamic Determinant
Computation Vissarion Fisikopoulos and Luis Peńaranda
MORPH-PRO: A Novel Algorithm and Web Server for Protein Morphing
Natalie E. Castellana, Andrey Lushnikov, Piotr Rotkiewicz, Natasha Sefcovic, Pavel A.
Pevzner, Adam Godzik and Kira Vyatkina
Finding a maximum induced degenerate subgraph faster than 2n Marcin Pilipczuk and Michał Pilipczuk
10:55 A Model for Minimizing Active Processor Time Jessica Chang, Harold Gabow and Samir Khuller
Improved
Implementation of Point Location in General Two-Dimensional Subdivisions Michael Hemmer, Michal Kleinbort and Dan Halperin
How Accurately Can We Model Protein Structures with Dihedral Angles?
Xuefeng Cui, Shuai Cheng Li, Dongbo Bu, Babak Alipanahi Ramandi and Ming Li
Instance Compression for the Polynomial Hierarchy and Beyond Chiranjit Chakraborty and Rahul Santhanam
Wednesday
11:20 On the Value of Job Migration in Online Makespan Minimization Susanne Albers and Matthias Hellwig
On Computing Straight Skeletons by Means of Kinetic Triangulations Peter Palfrader, Martin Held and Stefan Huber
Resolving Spatial Inconsistencies in Chromosome Conformation Data Geet Duggal, Rob Patro, Emre Sefer, Hao Wang, Darya Filippova, Samir Khuller and Carl Kingsford
A New Algorithm for Parameterized MAX- SAT
Ivan Bliznets and Alexander Golovnev
11:45 Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates Thomas Kesselheim
Lines Through Segments in 3D Space
Efi Fogel, Michael Hemmer, Asaf Porat and Dan Halperin
MS-DPR: An Algorithm for Computing Statistical Significance of Spectral
Identifications of Non- linear Peptides Hosein Mohimani, Sangtae Kim and Pavel A. Pevzner
12:10
Lunch Restaurant ESA I – White Hall
Chair: Andrej Brodnik Data structures 1
ESA II – Glass Hall 2+3 Chair: Vincenzo Bonifaci Approximation algorithms for graphs
WABI – Glass Hall 1 Chair: Leo van Iersel Phylogenetic Trees 2
IPEC – Red Hall Chair: Dimitrios M.
Thilikos Tutorial 13:30 Explicit and Efficient
Hash Families Suffice for Cuckoo Hashing with a Stash
Martin Aumüller, Martin Dietzfelbinger and Philipp Woelfel
A Dual-Fitting 3/2- Approximation Algorithm for Some Minimum-Cost Graph Problems
James Davis and David Williamson
An Optimal
Reconciliation Algorithm for Gene Trees with Polytomies
Manuel Lafond, Krister M. Swenson and Nadia El-Mabrouk
Subexponential Parameterised Algorithms Saket Saurabh
Wednesday
13:55 Succinct Posets J. Ian Munro and Patrick K. Nicholson
TSP tours in Cubic Graphs: Beyond 4/3 Jose A. Soto, Jose R.
Correa and Omar Larre
Accounting for Gene Tree Uncertainties Improves Gene Trees and Reconciliation Inference
Thi Hau Nguyen, Jean- Philippe Doyon, Stéphanie Pointet, Anne-Muriel Arigon Chifolleau, Vincent Ranwez and Vincent Berry
14:20 On online labeling with polynomially many labels Martin Babka, Jan Bulánek, Michal Koucký, Vladimír Čunát and Michael Saks
On Min-Power Steiner Tree
Fabrizio Grandoni
Extracting Conflict-Free Information from Multi- labeled Trees
Akshay Deepak, David Fernández-Baca and Michelle M. McMahon
14:45
Coffee break Blue room ESA I – White Hall
Chair: Alejandro López- Ortiz
Data structures 2
ESA II – Glass Hall 2+3 Chair: Samir Khuller Optimization
WABI – Glass Hall 1 Chair: Rayan Chikhi Tree Analysis
IPEC – Red Hall Chair: Michał Pilipczuk IPEC 2
15:15 A Self-Adjusting Data Structure for Multidimensional Point Sets
Eunhui Park and David Mount
Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
Tim Nonner
A Practical Approximation Algorithm for Solving Massive Instances of Hybridization Number Leo van Iersel, Steven Kelk, Nela Lekić and Celine Scornavacca
New results on polynomial inapproximability and fixed parameter approximability of EDGE DOMINATING SET Bruno Escoffier, Jérôme Monnot, Vangelis Paschos and Mingyu Xiao
15:40
Data Structures on Event Graphs Bernard Chazelle and Wolfgang Mulzer
Optimizing over the Growing Spectrahedron Joachim Giesen, Martin Jaggi and Soeren Laue
Succinct Multibit Tree:
Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches Yasuo Tabei
Restricted and Swap Common Superstring: a Parameterized View Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis
