5,142 Works

Search as Learning (Dagstuhl Seminar 17092)

Kevyn Collins-Thompson, Preben Hansen & Claudia Hauff
This report describes the program and the results of Dagstuhl Seminar 17092 "Search as Learning", which brought together 26 researchers from diverse research backgrounds. The motivation for the seminar stems from the fact that modern Web search engines are largely engineered and optimized to fulfill lookup tasks instead of complex search tasks. The latter though are an essential component of information discovery and learning. The 3-day seminar started with four perspective talks, providing four different...

Computer Science Meets Ecology (Dagstuhl Seminar 17091)

Gustau Camps-Valls, Thhomas Hickler & Birgitta König-Ries
This report summarizes the program and main outcomes of the Dagstuhl Seminar 17091 entitled ``Computer Science Meets Ecolog''. Ecology is a discipline that poses many challenging problems involving big data collection, provenance and integration, as well as difficulties in data analysis, prediction and understanding. All these issues are precisely the arena where computer science is concerned. The seminar motivation was rooted in the belief that ecology could largely benefit from modern computer science. The seminar...

Shape-Changing Interfaces (Dagstuhl Seminar 17082)

Jason Alexander, Sean Follmer, Kasper Hornbaek & Anne Roudaut
Shape-changing interfaces use physical shape change as input and output; such interfaces are emerging as an alternative way of interacting with computers. This seminar brought together researchers working on shape-changing interfaces to discuss three key themes: (1) The technologies involved in shape-change, including soft and modular robotics, smart materials, and mechanical actuation. (2) The design of shape-changing interfaces, including their key application areas, and their industrial and interaction design. (3) The user experience of shape-changing...

Computability Theory (Dagstuhl Seminar 17081)

Klaus Ambos-Spies, Vasco Brattka, Rodney Downey & Steffen Lempp
Computability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and its applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of...

Computer-Assisted Engineering for Robotics and Autonomous Systems (Dagstuhl Seminar 17071)

Erika Abraham, Hadas Kress-Gazit, Lorenzo Natale & Armando Tacchella
This report documents the program and the outcomes of Dagstuhl Seminar 17071 "Computer-Assisted Engineering for Robotics and Autonomous Systems". This seminar brought together researchers from three distinct communities -- Robotics, Model-driven Software Engineering, and Formal Methods -- to discuss the path towards creating safe and verifiable autonomous systems.

Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072)

Benjamin Burton, Maarten Löffler, Carola Wenk & Erin Moriarty Wolf Chambers
This report documents the program and the outcomes of Dagstuhl Seminar 17072 "Applications of Topology to the Analysis of 1-Dimensional Objects".

Flight Planning in Free Route Airspaces

Casper Kehlet Jensen, Marco Chiarandini & Kim S. Larsen
We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined...

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

Trivikram Dokka & Marc Goerigk
Through the development of efficient algorithms, data structures and preprocessing techniques, real-world shortest path problems in street networks are now very fast to solve. But in reality, the exact travel times along each arc in the network may not be known. This led to the development of robust shortest path problems, where all possible arc travel times are contained in a so-called uncertainty set of possible outcomes. Research in robust shortest path problems typically assumes...

Integrating Passengers' Assignment in Cost-Optimal Line Planning

Markus Friedrich, Maximilian Hartl, Alexander Schiewe & Anita Schöbel
Finding a line plan with corresponding frequencies is an mportant stage of planning a public transport system. A line plan should permit all passengers to travel with an appropriate quality at appropriate costs for the public transport operator. Traditional line planning procedures proceed sequentially: In a first step a traffic assignment allocates passengers to routes in the network, often by means of a shortest path assignment. The resulting traffic loads are used in a second...

Strong Relaxations for the Train Timetabling Problem Using Connected Configurations

Frank Fischer & Thomas Schlechte
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by...

Optimizing Traffic Signal Settings for Public Transport Priority

Robert Scheffler & Martin Strehler
In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclically time-expanded network model for the combined traffic assignment traffic signal coordination problem, we introduce a suitable queuing model and several modifications to model public transport vehicles appropriately. We evaluate the applicability of this approach by computing and...

Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables

Fahimeh Khoshniyat & Johanna Törnquist Krasemann
A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week...

Optimizing Train Stopping Patterns for Congestion Management

Tatsuki Yamauchi, Mizuyo Takamatsu & Shinji Imahori
In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway...

Faster Transit Routing by Hyper Partitioning

Daniel Delling, Julian Dibbelt, Thomas Pajor & Tobias Zündorf
We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and...

Dynamic Time-Dependent Routing in Road Networks Through Sampling

Ben Strasser
We study the earliest arrival and profile problems in road networks with time-dependent functions as arc weights and dynamic updates. We present and experimentally evaluate simple, sampling-based, heuristic algorithms. Our evaluation is performed on large, current, production-grade road graph data with time-dependent arc weights. It clearly shows that the proposed algorithms are fast and compute paths with a sufficiently small error for most practical applications. We experimentally compare our algorithm against the current state-of-the-art. Our...

Improved Oracles for Time-Dependent Road Networks

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner & Christos Zaroliagis
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden...

Look-Ahead Approaches for Integrated Planning in Public Transportation

Julius Pätzold, Alexander Schiewe, Philine Schiewe & Anita Schöbel
In this paper we deal with three consecutive planning stages in public transportation: Line planning (including line pool generation), timetabling, and vehicle scheduling. These three steps are traditionally performed one after another in a sequential way often leading to high costs in the (last) vehicle scheduling stage. In this paper we propose three different ways to "look ahead", i.e., to include aspects of vehicle scheduling already earlier in the sequential process: an adapted line pool...

Cost Projection Methods for the Shortest Path Problem with Crossing Costs

Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte & Swen Schlobach
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an...

Public Transit Routing with Unrestricted Walking

Dorothea Wagner & Tobias Zündorf
We study the problem of answering profile queries in public transportation networks that allow unrestricted walking. That is, finding all Pareto-optimal journeys regarding travel time and number of transfers in a given time interval. We introduce a novel algorithm that, unlike most state-of-the-art algorithms, can compute profiles efficiently in a setting that allows arbitrary walking. Using our algorithm, we show in an extensive experimental study that allowing unrestricted walking, significantly reduces travel times, compared to...

An Improved Algorithm for the Periodic Timetabling Problem

Marc Goerigk & Christian Liebchen
We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This...

Robustness Tests for Public Transport Planning

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe & Anita Schöbel
The classical planning process in public transport planning focuses on the two criteria operating costs and quality for passengers. Quality mostly considers quantities like average travel time and number of transfers. Since public transport often suffers from delays caused by random disturbances, we are interested in adding a third dimension: robustness. We propose passenger-oriented robustness indicators for public transport networks and timetables. These robustness indicators are evaluated for several public transport plans which have been...

Truthful Mechanisms for Delivery with Agents

Andreas Bärtschi, Daniel Graf & Paolo Penna
We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ packages (physical objects) which have to be transported between specified source-target pairs in an undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one package at a time. Following a recent model [Baertschi et al. 2017], each agent i has a different rate of energy consumption per unit distance traveled,...

Front Matter, Table of Contents, Preface, Organization

Gianlorenzo D'Angelo & Twan Dollevoet
Front Matter, Table of Contents, Preface, Organization

Revenue Maximization in Online Dial-A-Ride

Ananya Christman, Christine Chung, Nicholas Jaczko, Marina Milan, Anna Vasilchenko & Scott Westvold
We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server's goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive...

A New Notion of Compositionality for Concurrent Program Proofs (Invited Talk)

Azadeh Farzan & Zachary Kincaid
This paper presents a high level overview of Proof Spaces [Farzan, Kincaid, and Podelski, 2015] as an instance of a new approach to compositional verification of concurrent programs and discusses potential future work extending the approach beyond its current scope of applicability.

Resource Types

  • Text
  • Software

Publication Year

  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006