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.