TY - JOUR
T1 - On the complexity of the highway problem
AU - Elbassioni, Khaled
AU - Raman, Rajiv
AU - Ray, Saurabh
AU - Sitters, René
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012/11/16
Y1 - 2012/11/16
N2 - In the highway problem, we are given a path, and a set of buyers interested in buying sub-paths of this path; each buyer declares a non-negative budget, which is the maximum amount of money she is willing to pay for that sub-path. The problem is to assign non-negative prices to the edges of the path such that we maximize the profit obtained by selling the edges to the buyers who can afford to buy their sub-paths, where a buyer can afford to buy her sub-path if the sum of prices in the sub-path is at most her budget. In this paper, we show that the highway problem is strongly NP-hard; this settles the complexity of the problem in view of the existence of a polynomial-time approximation scheme, as was recently shown in Grandoni and Rothvoß (2011) [15]. We also consider the coupon model, where we allow some items to be priced below zero to improve the overall profit. We show that allowing negative prices makes the problem APX-hard. As a corollary, we show that the bipartite vertex pricing problem is APX-hard with budgets in 1,2,3, both in the cases with negative and non-negative prices.
AB - In the highway problem, we are given a path, and a set of buyers interested in buying sub-paths of this path; each buyer declares a non-negative budget, which is the maximum amount of money she is willing to pay for that sub-path. The problem is to assign non-negative prices to the edges of the path such that we maximize the profit obtained by selling the edges to the buyers who can afford to buy their sub-paths, where a buyer can afford to buy her sub-path if the sum of prices in the sub-path is at most her budget. In this paper, we show that the highway problem is strongly NP-hard; this settles the complexity of the problem in view of the existence of a polynomial-time approximation scheme, as was recently shown in Grandoni and Rothvoß (2011) [15]. We also consider the coupon model, where we allow some items to be priced below zero to improve the overall profit. We show that allowing negative prices makes the problem APX-hard. As a corollary, we show that the bipartite vertex pricing problem is APX-hard with budgets in 1,2,3, both in the cases with negative and non-negative prices.
KW - Approximation algorithms
KW - Complexity
KW - Hardness of approximation
KW - Interval graphs
KW - NP-hardness
KW - Pricing
UR - http://www.scopus.com/inward/record.url?scp=84867336314&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867336314&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.07.028
DO - 10.1016/j.tcs.2012.07.028
M3 - Article
AN - SCOPUS:84867336314
VL - 460
SP - 70
EP - 77
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -