CIAC 2017
10th International Conference on Algorithms and Complexity
May 24-26, Athens, Greece
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 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-ObaStructural Parameters for Scheduling with Assignment Restrictions Yuval Emek, Yaacov Shapiro and Yuyi WangMinimum Cost Perfect Matching with Delays for Two Sources Toshihiro FujitoApproximating Bounded Degree Deletion via Matroid Matching Aritra Banik, Matthew Katz, Eli Packer and Marina SimakovTracking 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 SkopalikCongestion Games with Complementarities Pieter Kleer and Guido SchaeferTight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games Martin Gairing, Konstantinos Kollias and Grammateia KotsialouCost-Sharing in Generalized Selfish Routing Themistoklis Melissourgos and Paul SpirakisExistence 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 ZandenOn the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs Lars Jaffke and Bart M. P. JansenFine-Grained Parameterized Complexity Analysis of Graph Coloring Problems Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar TalePaths 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 WattenhoferCollaboration without Communication: Evacuating Two Robots from a Disk Klaus-Tycho Förster, Linus Groner, Torsten Hoefler, Michael König, Sascha Schmid and Roger WattenhoferMulti-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 ShendeLinear Search with Terrain-Dependent Speeds Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Jan Manuch, Lata Narayanan, Jaroslav Opatrny and Ladislav StachoWeak 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 SorgeAssessing 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 WatrigantParameterized Resiliency Problems via Integer Linear Programming Erik D. Demaine, Isaac Grosof and Jayson LynchPush-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 GeissmannCache Oblivious Minimum Cut Konstantinos Mastakas and Antonios SymvonisRooted Uniform Monotone Minimum Spanning Trees Oylum Şeker, Pinar Heggernes, Tınaz Ekim and Z. Caner TaşkınLinear-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 SchewePerpetually Dominating Large Grids Cristina Bazgan, Thomas Pontoizeau and Zsolt TuzaOn the complexity of finding a potential community Yuya Higashikawa, Keiko Imai, Yusuke Matsumoto, Noriyoshi Sukegawa and Yusuke YokosukaMinimum 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 ZachosCompleteness results for counting problems with easy decision Sascha BrauerComplexity 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 WuOn 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 2017We 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; 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.
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.
Previous Conferences:
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.