Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We consider the Stackelberg shortest-path pricing problem, which is definedas follows. Given a graph G with fixed-cost and pricable edges and two distinctvertices s and t, we may assign prices to the pricable edges. Based on thepredefined fixed costs and our prices, a customer purchases a cheapest s-t-pathin G and we receive payment equal to the sum of prices of pricable edgesbelonging to the path. Our goal is to find prices maximizing the paymentreceived from the customer. While Stackelberg shortest-path pricing was knownto be APX-hard before, we provide the first explicit approximation thresholdand prove hardness of approximation within 2-o1.



Autor: Patrick Briest, Sanjeev Khanna

Fuente: https://arxiv.org/







Documentos relacionados