TY - GEN

T1 - A QPTAS for-envy-free profit-maximizing pricing on line graphs

AU - Elbassioni, Khaled

PY - 2012

Y1 - 2012

N2 - We consider the problem of pricing edges of a line graph so as to maximize the profit made from selling intervals to single-minded customers. An instance is given by a set E of n edges with a limited supply for each edge, and a set of m clients, where each client j specifies one interval of E she is interested in and a budget B j which is the maximum price she is willing to pay for that interval. An envy-free pricing is one in which every customer is allocated (possibly empty) interval maximizing her utility. Recently, Grandoni and Rothvoss (SODA 2011) gave a polynomial-time approximation scheme (PTAS) for the unlimited supply case with running time. By utilizing the known hierarchical decomposition of doubling metrics, we give a PTAS with running time. We then consider the limited supply case, and the notion of-envy-free pricing in which a customer gets an allocation maximizing her utility within an additive error of. For this case we develop an approximation scheme with running time, where is the maximum ratio of the budgets of any two customers demanding edge e. This yields a PTAS in the uniform budget case, and a quasi-PTAS for the general case.

AB - We consider the problem of pricing edges of a line graph so as to maximize the profit made from selling intervals to single-minded customers. An instance is given by a set E of n edges with a limited supply for each edge, and a set of m clients, where each client j specifies one interval of E she is interested in and a budget B j which is the maximum price she is willing to pay for that interval. An envy-free pricing is one in which every customer is allocated (possibly empty) interval maximizing her utility. Recently, Grandoni and Rothvoss (SODA 2011) gave a polynomial-time approximation scheme (PTAS) for the unlimited supply case with running time. By utilizing the known hierarchical decomposition of doubling metrics, we give a PTAS with running time. We then consider the limited supply case, and the notion of-envy-free pricing in which a customer gets an allocation maximizing her utility within an additive error of. For this case we develop an approximation scheme with running time, where is the maximum ratio of the budgets of any two customers demanding edge e. This yields a PTAS in the uniform budget case, and a quasi-PTAS for the general case.

UR - http://www.scopus.com/inward/record.url?scp=84867335062&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31585-5_46

DO - 10.1007/978-3-642-31585-5_46

M3 - Conference contribution

AN - SCOPUS:84867335062

SN - 9783642315848

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 513

EP - 524

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

PB - Springer Verlag

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -