Title: Balancing profits and costs on trees
Authors: Coene, Sofie ×
Filippi, C.
Spieksma, Frits
Stevanato, E. #
Issue Date: 2013
Publisher: Wiley
Series Title: Networks vol:61 issue:3 pages:200-211
Abstract: We consider a rooted tree graph with costs associated with the edges and profits associated with the vertices. Every subtree containing the root incurs the sum of the costs of its edges, and collects the sum of the profits of its nodes; the goal is the simultaneous minimization of the total cost and maximization of the total profit. This problem is related to the TSP with profits on graphs with a tree metric. We analyze the problem from a biobjective point of view. We show that finding all extreme supported efficient points can be done in polynomial time. The problem of finding all efficient points, however, is harder; we propose a practical FPTAS for solving this problem. Some special cases are considered where the particular profit/cost structure or graph topology allows the efficient points to be found in polynomial time. Our results can be extended to more general graphs with distance matrices satisfying the Kalmanson conditions
ISSN: 0028-3045
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
Balancingprofits.pdf Published 233KbAdobe 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