Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Approximation algorithms for time-dependent orienteering

In English

Författare

Summary, in English

The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For ε greater than or equal 0, we provide a (2+ ε)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.

Avdelning/ar

  • Computer Science

Publiceringsår

2002

Språk

Engelska

Sidor

57-62

Publikation/Tidskrift/Serie

Information Processing Letters

Volym

83

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

Elsevier

Ämne

  • Computer Science

Nyckelord

  • Problem solving
  • Theorem proving
  • Optimization
  • Time-dependent orienteering
  • Algorithms
  • Polynomial approximation
  • Traveling salesman problem

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0020-0190