Seminar & CEID social hour
Date-place: Friday 31st May, 3-5pm, Building Β (Room AS)
Speaker: Spyros Kontogiannis, Associate Professor, Computer Science & Engineering Department, University of Ioannina
Title: Engineering Travel-Time Oracles for Time-Dependent Road Networks: A Combinatorial Perspective
Summary: A novel landmark-based oracle (CFLAT) is designed, analyzed and engineered, for providing earliest-arrival-time routes in time-dependent road networks. The preprocessesed information consists of combinatorial structures (i.e., collections of time-stamped min-travel-time-path trees) rather than approximations of travel-time functions. This information is then exploited by a novel query algorithm (CFCA) which computes (and has to pay for it) the actual connecting path that preserves the theoretical approximation guarantees. Some recent algorithmic improvements are also presented. A thorough experimental evaluation on two real-world benchmark instances, as well as a typical synthetic benchmark, shows that CFLAT achieves significant improvements on the preprocessing requirements, approximation guarantee and query-time for providing earliest-arrival-time paths, in comparison to previous landmark-based oracles. It also achieves quite competitive query-time performance, compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction
About the speaker: Spyros Kontogiannis obtained his Diploma (1989, as well as his Phd (2000) from the Computer Engineering and Informatics Department at the University of Patras. Consequently, he worked as a Postdoc (2000-2002) and as a research associate (2002-2003) at the Max Planck Institute of Informatics. Since 2004 he works at the University of Ioannina, currently being an Associate Professor at the Department of Computer Science and Engineering. He is also a senior research associate of CTI. He also has a regular collaboration with the Institute of Theoretical Informatics at the Karlsruhe Institute of Technology, and in particular with Prof. Wagner’s research group. His research interests lie mainly in the fields of design and analysis of algorithms, algorithmic game theory, algorithm engineering, large-scale network optimization, decentralized algorithms, and transportation systems. He has published more than 50 articles in major international journals, conferences and collective volumes, which have received more than 1000 citations. He is editor of the ALGORITHMS journal (MDPI), and has served in several Program and Organizing Committees of leading international computer science conferences. He has participated as a key researcher in more than 15 research projects funded by EC or by the Greek State, including H2020 SMARTBUY, CIP7 HoPE, FP7 MOVESMART, FP7 eCOMPASS, FP6 DELIS, FP6 ARRIVAL and FP5 CRESCCO.
http://www.cs.uoi.gr/~kontog/docs/kontog-cv4web.pdf
Photos might be posted on the site and Facebook page.
Thanks to Citrix for the kind support of our events.