REAL

Multi-criteria approximation schemes for the resource constrained shortest path problem

Horváth, Markó and Kis, Tamás (2017) Multi-criteria approximation schemes for the resource constrained shortest path problem. OPTIMIZATION LETTERS. ISSN 1862-4472 (Submitted)

[img]
Preview
Text
43_horvath_kis.pdf

Download (308kB) | Preview

Abstract

In the resource constrained shortest path problem we are given a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resources with finite budget limits. A minimum cost source-destination path is sought such that the total consumption of the arcs from each resource does not exceed its budget limit. In the case of constant number of weight functions we give a fully polynomial time multi-criteria approximation scheme for the problem which returns a source-destination path of cost at most the optimum, however, the path may slightly violate the budget limits. On the negative side, we show that there does not exist polynomial time multi-criteria approximation scheme for the problem if the number of weight functions is not a constant. The latter result applies to a broad class of problem as well, including the multi-dimensional knapsack, the multi-budgeted spanning tree, the multi-budgeted matroid basis and the multi-budgeted bipartite perfect matching problems.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Dr. Tamás Kis
Date Deposited: 16 Sep 2017 10:35
Last Modified: 05 Apr 2023 06:37
URI: http://real.mtak.hu/id/eprint/62592

Actions (login required)

Edit Item Edit Item