CIAC 2017

10th International Conference on Algorithms and Complexity
May 24-26, Athens, Greece

The conference is now over. Many thanks to all participants, the invited speakers, the committees members, the sponsors, and all those involved in various organizational tasks; the contribution of each to the success of the conference has been indispensable.

General

Aims and Scope

The International Conference on Algorithms and Complexity is intended to provide a forum for researchers working in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures. The 10th International Conference on Algorithms and Complexity (CIAC 2017) will take place in Athens, Greece, on May 24-26, 2017.

Topics

Papers presenting original research in the areas of algorithms and complexity are sought, including (but not limited to):

  • sequential, parallel and distributed algorithms and data structures
  • approximation and randomized algorithms
  • graph algorithms and graph drawing
  • on-line and streaming algorithms
  • analysis of algorithms and computational complexity
  • algorithm engineering
  • web algorithms
  • exact and parameterized computation
  • algorithmic game theory
  • computational biology
  • foundations of communication networks
  • computational geometry
  • discrete optimization

Important Dates

  • Deadline for early registration: April 10, 2017
  • Deadline for submission extended to: November 11, 2016, 23:59 AoΕ
  • Notification of acceptance: December 20, 2016
  • Final manuscript, camera ready: January 31, 2017
  • Conference: May 24-26, 2017

Invited Speakers

  • Giuseppe Italiano, Università di Roma 2, Italy
  • Klaus Jansen, University of Kiel, Germany
  • Christos Papadimitriou, University of California Berkeley, USA

Best Paper Award

This year there will be a CIAC 2017 Best Paper Award, accompanied by a prize of EUR 1,000 offered by Springer.

Proceedings

The conference proceedings appear in Springer Lecture Notes in Computer Science series, volume 10236
CIAC 2017, LNCS 10236

Conference handbook

This leaflet contains information about the conference and a short guide to Athens.

Sponsors

NTUA_ECE
ICCS
IEEEGR

SPRINGER
UPCOM

SIMMETRIA
EATCS


Program

Tuesday, May 23
18:30 - 19:30 Registration (ECE Building)
19:00 – 21:00 Reception (ECE Building)
Wednesday, May 24
8:00 - 8:45 Registration (main venue)
8:45 - 9:00 Opening Remarks
9:00 – 10:00 Invited Talk 1
Klaus Jansen

New Algorithmic Results for Bin Packing and Scheduling

10:00 – 10:30 Coffee Break
10:30 – 12:35 Session 1
Fidaa Abed, Lin Chen, Yann Disser, Martin Groß, Nicole Megow, Julie Meissner, Alexander Richter and Roman Rischke

Scheduling Maintenance Jobs in Network

Klaus Jansen, Marten Maack and Roberto Solis-Oba

Structural Parameters for Scheduling with Assignment Restrictions

Yuval Emek, Yaacov Shapiro and Yuyi Wang

Minimum Cost Perfect Matching with Delays for Two Sources

Toshihiro Fujito

Approximating Bounded Degree Deletion via Matroid Matching

Aritra Banik, Matthew Katz, Eli Packer and Marina Simakov

Tracking Paths

12:35 – 14:00 Lunch Break
14:00 – 16:05 Session 2
Laurent Gourves and Jerome Monnot

Approximate Maximin Share Allocations in Matroids

Matthias Feldotto, Lennart Leder and Alexander Skopalik

Congestion Games with Complementarities

Pieter Kleer and Guido Schaefer

Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games

Martin Gairing, Konstantinos Kollias and Grammateia Kotsialou

Cost-Sharing in Generalized Selfish Routing

Themistoklis Melissourgos and Paul Spirakis

Existence of evolutionarily stable strategies remains hard to decide for a wide range of payoff values

16:05 – 16:40 Coffee Break
16:40 – 18:20 Session 3
Petr Golovach, Dieter Kratsch and Mohamed Yosri Sayadi

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs

Sándor Kisfaludi-Bak and Tom C. van der Zanden

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs

Lars Jaffke and Bart M. P. Jansen

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar Tale

Paths to Trees and Cacti

Thursday, May 25
9:00 – 10:00 Invited Talk 2
Giuseppe F. Italiano

2-Edge and 2-Vertex Connectivity in Directed Graphs

10:00 – 10:30 Coffee Break
10:30 – 12:35 Session 4
Giovanni Viglietta, Giuseppe Antonio Di Luna, Paola Flocchini, Taisuke Izumi, Tomoko Izumi and Nicola Santoro

Population Protocols with Faulty Interactions: the Impact of a Leader

Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz and Roger Wattenhofer

Collaboration without Communication: Evacuating Two Robots from a Disk

Klaus-Tycho Förster, Linus Groner, Torsten Hoefler, Michael König, Sascha Schmid and Roger Wattenhofer

Multi-Agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds

Jaroslav Opatrny, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Sunil Shende

Linear Search with Terrain-Dependent Speeds

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Jan Manuch, Lata Narayanan, Jaroslav Opatrny and Ladislav Stacho

Weak Coverage of a Rectangular Barrier

12:35 – 14:00 Lunch Break
14:00 – 14:50 Session 5 (Best Paper awards)
Hans L. Bodlaender and Tom C. van der Zanden

Improved Lower Bounds for Graph Embedding Problems

Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier and Manuel Sorge

Assessing the Computational Complexity of Multi-Layer Subgraph Detection

14:50 – 15:30 Coffee Break
15:30 – 16:45 Session 6
Martin Fürer

On the Combinatorial Power of the Weisfeiler-Lehman Algorithm

Jason Crampton, Gregory Gutin, Martin Koutecký and Rémi Watrigant

Parameterized Resiliency Problems via Integer Linear Programming

Erik D. Demaine, Isaac Grosof and Jayson Lynch

Push-Pull Block Puzzles are Hard

16:45 – 16:50 Short Break
16:50 – 17:40 Special Session Dedicated to the 70th Birthday of Stathis Zachos
18:00 – 22:30 Visit to Vorres Museum (Paiania) and Conference Dinner at Mare Nostrum (Vravrona): coach from Conference Venue at 18:00, return to Syntagma square by 23:30.
Friday, May 26
9:30 – 10:30 Invited Talk 3
Christos H. Papadimitriou

TFNP: An Update

10:30 – 11:00 Coffee Break
11:00 – 12:40 Session 7
Torben Hagerup, Frank Kammer and Moritz Laudahn

Space-Efficient Euler Partition and Bipartite Edge Coloring

Lukas Gianinazzi and Barbara Geissmann

Cache Oblivious Minimum Cut

Konstantinos Mastakas and Antonios Symvonis

Rooted Uniform Monotone Minimum Spanning Trees

Oylum Şeker, Pinar Heggernes, Tınaz Ekim and Z. Caner Taşkın

Linear-time generation of random chordal graphs

12:40 – 14:00 Lunch Break
14:00 – 15:40 Session 8
Eleni C. Akrida, Jurek Czyzowicz, Leszek Gasieniec, Lukasz Kuszner and Paul Spirakis

Temporal flows in temporal networks

Ioannis Lamprou, Russell Martin and Sven Schewe

Perpetually Dominating Large Grids

Cristina Bazgan, Thomas Pontoizeau and Zsolt Tuza

On the complexity of finding a potential community

Yuya Higashikawa, Keiko Imai, Yusuke Matsumoto, Noriyoshi Sukegawa and Yusuke Yokosuka

Minimum Point-Overlap Labeling

15:40 – 16:10 Coffee Break
16:10 – 17:50 Session 9
Nader Bshouty and Ariel Gabizon

Almost Optimal Cover-Free Families

Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos and Stathis Zachos

Completeness results for counting problems with easy decision

Sascha Brauer

Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee and Bang Ye Wu

On the complexity of the star p-hub center problem with parameterized triangle inequality

17:50 – 18:00 Concluding Remarks


Committees

Program Committee

  • Vincenzo Bonifaci, IASI-CNR, Rome, Italy
  • Jarek Byrka, University of Wroclaw, Poland
  • Tiziana Calamoneri, Università di Roma I, "La Sapienza", Italy
  • Éric Colin de Verdière, CNRS and Université Paris-Est Marne-la-Vallée, France
  • Dimitris Fotakis, National Technical University of Athens, Greece
  • Thomas Erlebach, University of Leicester, UK
  • Irene Finocchi, Università di Roma I, "La Sapienza", Italy
  • Evangelos Kranakis, Carleton University, Canada
  • Dieter Kratsch, University of Lorraine, France
  • Michael Lampis, University Paris-Dauphine, France
  • Vangelis Markakis, Athens University of Economics and Business, Greece
  • Dániel Marx, Hungarian Academy of Science, Hungary
  • Monaldo Mastrolilli, IDSIA, Switzerland
  • Aris Pagourtzis, National Technical University of Athens, Greece
  • Vangelis Th. Paschos, University Paris-Dauphine, France (chair)
  • Francesco Pasquale, Università di Roma I, "La Sapienza", Italy
  • Giuseppe Persiano, Università di Salerno, Italy
  • Tomasz Radzik, King's College London, UK
  • Adi Rosén, CNRS and Université Paris Diderot, France
  • Guido Schäfer, CWI, Netherlands
  • Maria Serna, Universitat Politècnica de Catalunya, Spain
  • Paul Spirakis, University of Liverpool, UK and CTI, Greece
  • Angelika Steger, ETH Zurich, Switzerland
  • Ioan Todinca, University of Orleans, France
  • Andreas Wiese, Universidad de Chile, Chile

Best Paper Award Committee

  • Ljiljana Brankovic, University of Newcastle, Australia
  • Ralf Klasing, CNRS and University Bordeaux 1, France (chair)
  • Cécile Murat, University Paris-Dauphine, France
  • Vangelis Th. Paschos, University Paris-Dauphine, France
  • Peter Widmayer, ETH Zurich, Switzerland

Steering Committee

  • Giorgio Ausiello, Università di Roma I, "La Sapienza", Italy
  • Vangelis Paschos, University Paris-Dauphine, France
  • Rossella Petreschi, Università di Roma I, "La Sapienza", Italy
  • Paul Spirakis, University of Liverpool, UK and CTI, Greece
  • Peter Widmayer, ETH Zurich, Switzerland

Organizing Committee

  • Dimitris Fotakis, National Technical University of Athens (co-chair)
  • Euripides Markou, University of Thessaly
  • Ioannis Milis, Athens University of Economics and Business
  • Aris Pagourtzis, National Technical University of Athens (co-chair)
  • Dimitris Sakavalas, National Technical University of Athens
  • Vassilis Zissimopoulos, National and Kapodistrian University of Athens


Registration

There are different modalities of registration fees for CIAC 2017; all of them include the participation to all sessions on May 24-26, a copy of the proceedings, coffee breaks, lunches, a welcome reception and the social dinner. The registration fees for CIAC 2017 are described in the following table:

Early ( until April 10th ) Late ( until May 10th ) On-site (during the symposium)
Regular registration fee 380 Euros 450 Euros 480 Euros
Student registration fee 280 Euros 350 Euros 380 Euros

Acompanying persons can attend the social dinner; additional tickets will be available during the conference at the price of 50 euros.

Notice that for each accepted paper, at least one author must register.

Click here to register for CIAC 2017

Accommodation

We do not have any special deals with hotels, however some suggestions are listed below. Some of these hotels are relatively close to the conference venue (NTUA campus), while others are located in the city centre, with good connections (metro+bus) to NTUA campus. Please check the prices either from the hotel site directly or using the provided Booking link and pick the best option for you. We would also advise you to compare transportation options between the hotels and NTUA, according to your preferences (public transport, taxi, walking).

Hotel Hotel Website Booking Website
Hilton Athens Hilton Athens Website Booking Hilton
Divani Caravel Divani Caravel Website Booking Divani Caravel
Crowne Plaza Athens City Center Crowne Plaza Website Booking Crowne Plaza
Best Western Ilisia Hotel Best Western Ilisia Website Booking Best Western Ilisia
Airotel Stratos Vassilikos Airotel Stratos Vasilikos Website Booking Airotel Stratos Vasilikos
Golden Age Golden Age Website Booking Golden Age
Athinais Athinais Website Booking Athinais
Arethusa Arethusa Website Booking Arethusa
Pan Pan Website Booking Pan
Zappion Zappion Website Booking Zappion
Elizabeth hotel Elizabeth Website Booking Elizabeth
Family Inn Family Inn Website
President President Website Booking President
St George St George Website Booking St George
* Here is a map with the above hotels (kudos to Yaacov Shapiro for sharing this).



Venue

CIAC 2017 will take place in the Multimedia Amphitheater of the National Technical University of Athens (NTUA), located in the basement of NTUA's Central Library Building, close to the Electrical and Computer Engineering (ECE) Building. Reception and registration on May 23rd olny will take place in the ECE Building. See the map below:


You can arrive at the Central Library by various ways:

By public transport:

The easiest way is by taking the Blue Metro line (map) and getting off at the "ΚΑΤΕΧΑΚΗ" station. Then take the bus 242, get off at stop "ΘΥΡΩΡΕΙΟ" (you get off at the first stop inside the Campus) and walk 3 minutes towards the Central Library; please follow the signs on the "ΘΥΡΩΡΕΙΟ (THYROREIO)" bus stop.

Another option is to take the bus 140 from the "ΚΑΤΕΧΑΚΗ" metro station and get off at stop "ΠΟΛΥΤΕΧΝΕΙΟΥΠΟΛΗ". Then get into the campus and walk 7 minutes towards the Central Library.

By taxi:

Taxi from the Katechaki ("ΚΑΤΕΧΑΚΗ") Station to NTUA will cost aproximately 3,5 €.

By car:

You can use this google map to get directions from Alimou-Katechaki Avenue.




Submission Guidelines

Authors are invited to submit an extended abstract of at most 12 pages by 23:59 AoE, Friday, November 11, 2016 (deadline extended). Submissions are handled by EasyChair at the following web page:

https://easychair.org/conferences/?conf=ciac2017

Submission Format: An extended abstract submitted to CIAC 2017 should start with the title of the paper, each author's name, affiliation and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work. The extended abstract should not exceed 12 single-spaced pages (excluding references), using reasonable margins and at least 10-point font. If the authors believe that more details are essential to substantiate the claims of the paper, they may include a clearly marked appendix (with no space limit) that will be read at the discretion of the Program Committee. It is strongly recommended that submissions adhere to the specified format and length. Submissions that are clearly too long may be rejected immediately.

All submissions will be rigorously peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance.

The proceedings of the conference will be published by Springer-Verlag in the ARCoSS/LNCS series and will be available for distribution at the conference. Accepted papers will be allocated 12 pages total in the LNCS format in the proceedings. Submissions are encouraged, though not required, to follow the LNCS format. More information about the LNCS format can be found on the author instructions page of Springer-Verlag.



History

Previous Conferences:



Travel Information

Athens is easily accessible by air, sea, and road. Once there, the public transportation system provides a safe, dependable and efficient way to move around the city. The public transportation network consists of underground (metro), train, suburban railways, buses, trolley buses and trams. Athens is also connected with other parts of the mainland through a network of roads and railways. Timetables and other information are available here.

Visitors arriving by air will arrive to the Athens International Airport "Eleftherios Venizelos" (IATA code: ATH).

Visa requirements

Citizens of EU

EU Citizens do not need a visa to travel to Greece. In most cases a personal ID card will suffice to enter the country.

Non-EU Citizens

Greece is a member of the European Union and for most nationalities no visa is required.

Citizens of some countries need an entry visa for Greece.

If you need a visa, make sure to apply for one well in advance. To check current visa requirements or find the nearest Greek Embassy or Consulate , see information provided by the Greek Ministry of Foreign Affairs.

Other Information

Time zone

Greece is in the Eastern European Time Zone. Eastern European Standard Time (EET) is two hours ahead of Greenwich Mean Time (GMT+2). Like most countries in Europe, Summer (Daylight-Saving) Time is observed in Greece, where the time is shifted forward by 1 hour; 3 hours ahead of Greenwich Mean Time (GMT+3). Daylight-Saving time will be observed during the conference.

Currency

The national currency in Greece is the Euro.