Title: Profit-based latency problems on the line
Authors: Coene, Sofie ×
Spieksma, Frederik #
Issue Date: 2008
Publisher: North-Holland
Series Title: Operations Research Letters vol:36 issue:3 pages:333-337
Abstract: The latency problem with profits is a generalization of the minimum latency problem. In this generalization it is not necessary to visit all clients, however, visiting a
client may bring a certain revenue. More precisely, in the latency problem with profits, a server and a set of n clients, each with corresponding profit p_i (1 ≤ i ≤ n), are given. The single server is positioned at the origin at time t = 0 and travels with unit speed. When visiting a client, the server receives a revenue of p_i - t, with t the time at which the server reaches client i (1 ≤ i ≤ n). The goal is to select clients and find a route for the server such that total collected revenue is maximized. We formulate a dynamic programming algorithm to solve this problem when all clients are located on a line. We also consider the problem on the line with k servers and prove NP-completeness for the latency problem on the line with k non-identical servers and release dates. In this proof we also settle the complexity of an open problem in de Paepe et al. [4].
ISSN: 0167-6377
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
Profit-based latency problems on the line.pdfProfit-based latency problems on the line Published 329KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science