k-Link shortest paths in weighted subdivisions

Ovidiu Daescu; Joseph S B Mitchell; Simeon Ntafos; James D. Palmer; Chee K. Yap

k-Link shortest paths in weighted subdivisions

Ovidiu Daescu, Joseph S B Mitchell, Simeon Ntafos, James D. Palmer, Chee K. Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1 + ε) times the weighted length of an optimal k-link path, for any fixed ε > 0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science
Editors	F. Dehne, A. Lopez-Ortiz, J.-R. Sack
Pages	325-337
Number of pages	13
Volume	3608
State	Published - 2005
Event	9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: Aug 15 2005 → Aug 17 2005

Other

Other	9th International Workshop on Algorithms and Data Structures, WADS 2005
Country/Territory	Canada
City	Waterloo
Period	8/15/05 → 8/17/05

ASJC Scopus subject areas

Computer Science (miscellaneous)

Cite this

@inproceedings{6b7011f3143b486cafab0a66f0d19884,

title = "k-Link shortest paths in weighted subdivisions",

abstract = "We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1 + ε) times the weighted length of an optimal k-link path, for any fixed ε > 0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.",

author = "Ovidiu Daescu and Mitchell, {Joseph S B} and Simeon Ntafos and Palmer, {James D.} and Yap, {Chee K.}",

year = "2005",

language = "English (US)",

volume = "3608",

pages = "325--337",

editor = "F. Dehne and A. Lopez-Ortiz and J.-R. Sack",

booktitle = "Lecture Notes in Computer Science",

note = "9th International Workshop on Algorithms and Data Structures, WADS 2005 ; Conference date: 15-08-2005 Through 17-08-2005",

}

TY - GEN

T1 - k-Link shortest paths in weighted subdivisions

AU - Daescu, Ovidiu

AU - Mitchell, Joseph S B

AU - Ntafos, Simeon

AU - Palmer, James D.

AU - Yap, Chee K.

PY - 2005

Y1 - 2005

N2 - We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1 + ε) times the weighted length of an optimal k-link path, for any fixed ε > 0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.

AB - We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1 + ε) times the weighted length of an optimal k-link path, for any fixed ε > 0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.

UR - http://www.scopus.com/inward/record.url?scp=26844496069&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26844496069&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:26844496069

VL - 3608

SP - 325

EP - 337

BT - Lecture Notes in Computer Science

A2 - Dehne, F.

A2 - Lopez-Ortiz, A.

A2 - Sack, J.-R.

T2 - 9th International Workshop on Algorithms and Data Structures, WADS 2005

Y2 - 15 August 2005 through 17 August 2005

ER -

k-Link shortest paths in weighted subdivisions

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this