10th International Conference on Algorithms and Complexity
May 24-26, Athens, Greece
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.
Papers presenting original research in the areas of algorithms and complexity are sought, including (but not limited to):
This year there will be a CIAC 2017 Best Paper Award, accompanied by a prize of EUR 1,000 offered by Springer.
The conference proceedings appear in Springer Lecture Notes in Computer Science series, volume 10236
CIAC 2017, LNCS 10236
This leaflet contains information about the conference and a short guide to Athens.
|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
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 NetworkKlaus Jansen, Marten Maack and Roberto Solis-Oba
Structural Parameters for Scheduling with Assignment RestrictionsYuval Emek, Yaacov Shapiro and Yuyi Wang
Minimum Cost Perfect Matching with Delays for Two SourcesToshihiro Fujito
Approximating Bounded Degree Deletion via Matroid MatchingAritra Banik, Matthew Katz, Eli Packer and Marina Simakov
|12:35 – 14:00||Lunch Break|
|14:00 – 16:05||Session 2
Laurent Gourves and Jerome Monnot
Approximate Maximin Share Allocations in MatroidsMatthias Feldotto, Lennart Leder and Alexander Skopalik
Congestion Games with ComplementaritiesPieter Kleer and Guido Schaefer
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion GamesMartin Gairing, Konstantinos Kollias and Grammateia Kotsialou
Cost-Sharing in Generalized Selfish RoutingThemistoklis 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 GraphsSándor Kisfaludi-Bak and Tom C. van der Zanden
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk GraphsLars Jaffke and Bart M. P. Jansen
Fine-Grained Parameterized Complexity Analysis of Graph Coloring ProblemsAkanksha 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 LeaderSebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz and Roger Wattenhofer
Collaboration without Communication: Evacuating Two Robots from a DiskKlaus-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 BoundsJaroslav Opatrny, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Sunil Shende
Linear Search with Terrain-Dependent SpeedsStefan 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
Hans L. Bodlaender and Tom C. van der Zanden
Improved Lower Bounds for Graph Embedding ProblemsRobert 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
On the Combinatorial Power of the Weisfeiler-Lehman AlgorithmJason Crampton, Gregory Gutin, Martin Koutecký and Rémi Watrigant
Parameterized Resiliency Problems via Integer Linear ProgrammingErik 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)|
|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 ColoringLukas Gianinazzi and Barbara Geissmann
Cache Oblivious Minimum CutKonstantinos Mastakas and Antonios Symvonis
Rooted Uniform Monotone Minimum Spanning TreesOylum Ş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 networksIoannis Lamprou, Russell Martin and Sven Schewe
Perpetually Dominating Large GridsCristina Bazgan, Thomas Pontoizeau and Zsolt Tuza
On the complexity of finding a potential communityYuya 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 FamiliesEleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos and Stathis Zachos
Completeness results for counting problems with easy decisionSascha Brauer
Complexity of Single-Swap Heuristics for Metric Facility Location and Related ProblemsLi-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|
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
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|
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:
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.
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.
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:
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.
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).
EU Citizens do not need a visa to travel to Greece. In most cases a personal ID card will suffice to enter the country.
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.
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.
The national currency in Greece is the Euro.