Concept

Shortest path problem

Related publications (252)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Approximating connected facility location problems via Random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...

2008

Contractive distributed MPC for consensus in networks of single- and double-integrators

Giancarlo Ferrari Trecate

In this paper we propose an application of distributed model predictive control techniques to the problem of driving a group of autonomous agents towards a consensus point, i.e. a negotiated position in their state space. Agents are assumed to be governed ...

2008

Reducing Buffer Space in Multipath Schemes

Maysam Yabandeh, Sajjad Zarifzadeh

One major drawback of multipath transferring schemes, which is inspired by the usage of different paths with diverse delays, is the emergence of reordering among packets of a flow. This reordering brings some substantial problems (like larger delay and buf ...

2008

Column Generation for the Split Delivery VRP

Matteo Salani

In this paper we tackle a variation of the Vehicle Routing Problem (VRP) in which each customer can be served by more than one vehicle, each serving a fraction of its demand. This problem is known as the Split Delivery VRP (SDVRP). Due to the potential sav ...

2008

Constrained paths in the flip-graph of regular triangulations

Thomas Liebling, Lionel Pournin

We describe particular paths in the flip-graph of regular triangulations in any dimension. It is shown that any pair of regular triangulations is connected by a path along which none of their common faces are destroyed. As a consequence, we obtain the conn ...

2007

Approach to time dependence and reliability in dynamic route guidance

Yixing Chen

This paper presents a methodology for increasing the reliability of route suggestions in route guidance systems. The procedure, based on the A* path-finding algorithm and Chen's link penalty method, involves penalizing links with a high risk of being conge ...

National Academy of Sciences2007

Robust Optimization with Recovery: Application to Shortest Paths and Airline Scheduling

Michel Bierlaire, Matteo Salani, Niklaus Eggenberg

In this exploratory paper we consider a robust approach to decisional problems subject to uncertain data in which we have an additional knowledge on the strategy (algorithm) used to react to an unforeseen event or recover from a disruption. This is a typic ...

2007

Robust Optimization with Recovery: Application to Shortest Paths and Airline Scheduling

Michel Bierlaire, Matteo Salani, Niklaus Eggenberg

2007

Adaptive media streaming over multipath networks

Dan Jurca

With the latest developments in video coding technology and fast deployment of end-user broadband internet connections, real-time media applications become increasingly interesting for both private users and businesses. However, the internet remains a best ...

EPFL2007

Path invariants

Dirk Thilo Beyer

The success of software verification depends on the ability to find a suitable abstraction of a program automatically. We propose a method for automated abstraction refinement which overcomes some limitations of current predicate discovery schemes. In curr ...

2007