Variants of the Shortest Path Problem

  • The shortest path problem in which the \((s,t)\)-paths \(P\) of a given digraph \(G =(V,E)\) are compared with respect to the sum of their edge costs is one of the best known problems in combinatorial optimization. The paper is concerned with a number of variations of this problem having different objective functions like bottleneck, balanced, minimum deviation, algebraic sum, \(k\)-sum and \(k\)-max objectives, \((k_1, k_2)-max, (k_1, k_2)\)-balanced and several types of trimmed-mean objectives. We give a survey on existing algorithms and propose a general model for those problems not yet treated in literature. The latter is based on the solution of resource constrained shortest path problems with equality constraints which can be solved in pseudo-polynomial time if the given graph is acyclic and the number of resources is fixed. In our setting, however, these problems can be solved in strongly polynomial time. Combining this with known results on \(k\)-sum and \(k\)-max optimization for general combinatorial problems, we obtain strongly polynomial algorithms for a variety of path problems on acyclic and general digraphs.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS
Verfasserangaben:Lara Turner
URN (Permalink):urn:nbn:de:hbz:386-kluedo-27139
Titel des übergeordneten Werkes (Englisch):Variants of the Shortest Path Problem
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (140)
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):24.08.2011
Jahr der Veröffentlichung:2011
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):25.08.2011
Freies Schlagwort / Tag:
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 27.05.2011

$Rev: 13581 $