Balancing profits and costs on trees
| Autor: | Carlo Filippi, Elisa Stevanato, Frits C. R. Spieksma, Sofie Coene |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
Multiobjective combinatorial optimization Trees Traveling Salesman Problem with Profits Kalmanson conditions Complexity Computer Networks and Communications Total cost Maximization Tree (graph theory) Travelling salesman problem Combinatorics Hardware and Architecture Topological graph theory Minification Time complexity Software Distance matrices in phylogeny MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|