Campus Event Calendar: Surender Baswana (11/17/2003 in 46.1

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

All-pairs approximate shortest paths

Surender Baswana

Max-Planck-Institut für Informatik - AG 1

AG1 Mittagsseminar (others' work)

AG 1, AG 2, AG 3, AG 4

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Monday, 17 November 2003

13:30

30 Minutes

46.1 - MPII

024

Saarbrücken

Abstract

Given a graph with $m$ edges and $n$ vertices, there exist classical algorithms that require $\tilde{O}(mn)$ time for computing all-pairs shortest paths (APSP). All the existing algorithms for APSP that promise sub-cubic running time are based on fast matrix multiplication algorithms which are notoriously impractical. There is still no combinatorial algorithm that could achieve sub-cubic running time for APSP problem. Moreover, in order to answer any distance/shortest-path query in optimal time, all the existing algorithms for APSP problem store all-pairs distance/path information explicitly in a $n \times n$ matrix.

In the last ten years, many simple combinatorial algorithms have been designed that compute all-pairs approximate shortest paths (APASP) for undirected graphs. The objective for designing an algorithm for
APASP problem is to achieve sub-cubic preprocessing time and/or sub-quadratic space at the expense of introducing some additive and/or
multiplicative error in the shortest path.

The talk will address two important algorithms for APASP, and mention a few open problems in the area of all-pairs approximate shortest paths.

The source papers :
Paper 1:
D. Dor, S. Halperin, and U. Zwick
"All pairs almost shortest paths"
SIAM Journal on Computing, 29:1740--1759, 2000

Paper 2:
M. Thorup and U. Zwick
"Approximate distance oracles"
STOC Proceedings 2001, pages 183--192

Contact

Ingmar Weber

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Ingmar Weber, 11/13/2003 19:47 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis