Sökning: id:"swepub:oai:lup.lub.lu.se:30682cd4-e6b9-4ee4-a1bf-ab3f882b2376" >
Online and offline ...
Online and offline algorithms for the time-dependent TSP with time zones
-
- Brodén, Björn (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Hammar, M (författare)
-
- Nilsson, Bengt J (författare)
- Malmö högskola,Teknik och samhälle (TS)
-
(creator_code:org_t)
- 2004-03-29
- 2004
- Engelska.
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 39:4, s. 299-319
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://mau.diva-por...
-
https://mau.diva-por... (primary) (Raw object)
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- time dependencies
- online algorithms
- the traveling salesman problem
- the orienteering problem
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas