Concept

Shortest path problem

Related publications (252)

Multi-path content delivery: Efficiency analysis and optimization algorithms

The paper studies the benefits of multi-path content delivery from a rate-distortion efficiency perspective. We develop an optimization framework for computing transmission schedules for streaming media packets over multiple network paths that maximize the ...

Academic Press Inc Elsevier Science2012

Formation preserving path finding in 3-D terrains

Ali Galip Bayrak

Navigation of a group of autonomous agents that are required to maintain a formation is a challenging task which has not been studied much especially in 3-D terrains. This paper presents a novel approach to collision free path finding of multiple agents pr ...

Springer Verlag2012

Optimizing over the Growing Spectrahedron

Martin Jaggi

We devise a framework for computing an approximate solution path for an important class of parameterized semidefinite problems that is guaranteed to be ε-close to the exact solution path. The problem of computing the entire regularization path for matrix f ...

Springer Berlin Heidelberg2012

Degrees of freedom of sparsely connected wireless networks

Michael Christoph Gastpar, Naveen Goela

We investigate how the network connectivity can affect the degrees of freedom (DoF) of wireless networks. We consider a network of n source-destination (SD) pairs and assume that any two nodes are connected with a positive probability p, independent of oth ...

IEEE2012

On the estimation of arterial route travel time distribution with Markov chains

Nikolaos Geroliminis, Mohsen Ramezani Ghalenoei

Recent advances in the probe vehicle deployment offer an innovative prospect for research in arterial travel time estimation. Specifically, we focus on the estimation of probability distribution of arterial route travel time, which contains more informatio ...

Elsevier2012

Risk-averse shortest path problems

Daniel Kuhn, Grani Adiwena Hanasusanto

We investigate routing policies for shortest path problems with uncertain arc lengths. The objective is to minimize a risk measure of the total travel time. We use the conditional value-at-risk (CVaR) for when the arc lengths (durations) have known distrib ...

IEEE2012

On the second successive minimum of the Jacobian of a Riemann surface

To a compact Riemann surface of genus g can be assigned a principally polarized abelian variety (PPAV) of dimension g, the Jacobian of the Riemann surface. The Schottky problem is to discern the Jacobians among the PPAVs. Buser and Sarnak showed that the s ...

Springer Netherlands2012

Multiple Object Tracking using K-Shortest Paths Optimization

Pascal Fua, François Fleuret, Engin Türetken, Jérôme Berclaz

Multi-object tracking can be achieved by detecting objects in individual frames and then linking detections across frames. Such an approach can be made very robust to the occasional detection failure: If an object is not detected in a frame but is in previ ...

Institute of Electrical and Electronics Engineers2011

Valuable Detours: Least-Cost Anypath Routing

Martin Vetterli, Matthias Grossglauser, Henri Julien Dubois-Ferrière

In many networks, it is less costly to transmit a packet to any node in a set of neighbors than to one specific neighbor. This observation was previously exploited by opportunistic routing protocols by using single-path routing metrics to assign to each no ...

2011

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol

Patrick Thiran, Julien Pierre Sacha Herzen

We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

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.