Premium
Balancing profits and costs on trees
Author(s) -
Coene Sofie,
Filippi Carlo,
Spieksma Frits C. R.,
Stevanato Elisa
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21469
Subject(s) - maximization , mathematical optimization , profit maximization , steiner tree problem , mathematics , combinatorics , time complexity , computer science , graph , minification , profit (economics) , economics , microeconomics
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. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013