# 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.