### Abstract

Original language | English |
---|---|

Pages (from-to) | 70-77 |

Journal | Theoretical Computer Science |

Volume | 460 |

DOIs | |

Publication status | Published - 2012 |

### Fingerprint

### Cite this

*Theoretical Computer Science*,

*460*, 70-77. https://doi.org/10.1016/j.tcs.2012.07.028

}

*Theoretical Computer Science*, vol. 460, pp. 70-77. https://doi.org/10.1016/j.tcs.2012.07.028

**On the complexity of the highway problem.** / Sitters, R.A.; Elbassioni, K.M.; Raman, R; Ray, S.

Research output: Contribution to Journal › Article › Academic › peer-review

TY - JOUR

T1 - On the complexity of the highway problem

AU - Sitters, R.A.

AU - Elbassioni, K.M.

AU - Raman, R

AU - Ray, S.

PY - 2012

Y1 - 2012

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. © 2012 Elsevier B.V. All rights reserved.

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. © 2012 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.tcs.2012.07.028

DO - 10.1016/j.tcs.2012.07.028

M3 - Article

VL - 460

SP - 70

EP - 77

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -