Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Mahmoud Fouz: Item Pricing with Partial Orders

June 18, 2009, 10:15 a.m.
E 1 3, Room 415

We consider the multi-product pricing problem, where, given customer budgets for each item and a partial order on the items, the goal is to price the items such that the revenue is maximized while the prices satisfy the order. For the case when the partial order is the union of (disjoint) linear orders, we give an O(1)-approximation algorithm. Using this result, we can solve the non-single-minded highway problem within an approximation factor of O(log n).

This is joint work with Khaled Elbassioni.