Time filter

Source Type

Bonifaci V.,CNR Institute for System Analysis and Computer Science Antonio Ruberti | Mehlhorn K.,MPI for Informatics | Varma G.,Tata Institute of Fundamental Research
Journal of Theoretical Biology | Year: 2012

Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by Tero et al. (Journal of Theoretical Biology, 244, 2007, pp. 553-564) to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0-s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by Tero et al. and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years. © 2012 Elsevier Ltd. Source

Bertrand P.,Ecole Normale Superieure de Cachan | Lenzen C.,MPI for Informatics
Proceedings of the Workshop on Algorithm Engineering and Experiments | Year: 2015

In this work, we examine a generic class of simple distributed balls-into-bins algorithms. Exploiting the strong concentration bounds that apply to balls-into-bins games, we provide an iterative method to compute accurate estimates of the remaining balls and the load distribution after each round. Each algorithm is classified by (i) the load that bins accept in a given round, (ii) the number of messages each ball sends in a given round, and (iii) whether each such message is given a rank expressing the sender's inclination to commit to the receiving bin (if feasible). This novel ranking mechanism results in notable improvements, in particular in the number of balls that may commit to a bin in the first round of the algorithm. Simulations independently verify the correctness of the results and confirm that our approximation is highly accurate even for a moderate number of 106 balls and bins. Copyright © 2015. by the Society for Industrial and Applied Mathematics. Source

Geiger A.,MPI for Intelligent Systems | Geiger A.,Karlsruhe Institute of Technology | Lauer M.,Karlsruhe Institute of Technology | Wojek C.,MPI for Informatics | And 2 more authors.
IEEE Transactions on Pattern Analysis and Machine Intelligence | Year: 2014

In this paper, we present a novel probabilistic generative model for multi-object traffic scene understanding from movable platforms which reasons jointly about the 3D scene layout as well as the location and orientation of objects in the scene. In particular, the scene topology, geometry, and traffic activities are inferred from short video sequences. Inspired by the impressive driving capabilities of humans, our model does not rely on GPS, lidar, or map knowledge. Instead, it takes advantage of a diverse set of visual cues in the form of vehicle tracklets, vanishing points, semantic scene labels, scene flow, and occupancy grids. For each of these cues, we propose likelihood functions that are integrated into a probabilistic generative model. We learn all model parameters from training data using contrastive divergence. Experiments conducted on videos of 113 representative intersections show that our approach successfully infers the correct layout in a variety of very challenging scenarios. To evaluate the importance of each feature cue, experiments using different feature combinations are conducted. Furthermore, we show how by employing context derived from the proposed method we are able to improve over the state-of-the-art in terms of object detection and object orientation estimation in challenging and cluttered urban environments. © 2013 IEEE. Source

Even G.,Tel Aviv University | Medina M.,MPI for Informatics
Algorithmica | Year: 2016

We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model (Aiello et al. in SODA, pp 771–780 2003). In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an (Formula presented.) competitive ratio for uni-directional grids (where n denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range (Formula presented.). Our randomized algorithm achieves an expected competitive ratio of (Formula presented.) for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous (Formula presented.)-competitive ratio of Azar and Zachut (ESA, pp 484–495, 2005). © 2016 The Author(s) Source

Lenzen C.,MPI for Informatics | Patt-Shamir B.,Tel Aviv University
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | Year: 2015

We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. A deterministic (1 + ε)-approximation to APSP with running time O(ε-2nlogn) rounds. The best previously known algorithm was randomized and slower by a (log n) factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and that are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of o(n/ log n). In the relabeling model, we obtain the following results. A randomized O(k)-approximation to APSP, for any inateger k > 1, running in O(n1/2+1/k + D) rounds, where D is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximaation ratio from O(k log k) to O(k). Also, the new algorithm uses O(logn)-bit labels, which is asymptotically optimal. A randomized O(k)-approximation to APSP, for any integer k > 1, running in time O((nD)1/2 • n1/k + D) and producing compact routing tables of size labels consist of O(k log n) bits. This improves on the apaproximation ratio of (k2) for tables of that size achieved by the best previously known algorithm, which terminates faster, in O(n1/2+1/k + D) rounds. In addition, we improve on the time complexity of the best known deterministic algorithm for distributed approximate Steiner forest. © Copyright 2015 ACM. Source

Discover hidden collaborations