Abstract: Multi-item auctions are auctions in which an auctioneer wants to sell a set of indivisible items. They have gained increasing scientific interest in economics, computer science, and recently in combinatorial optimization. This is due to applications in electronic marketplaces, and market-based mechanisms for resource allocation problems in production and transportation. A combinatorial auction is a multi-item auction in which bidders can make bids for subsets of items. Combinatorial auctions have superior economic properties if bidders have valuations for subsets of items that differ from the sum of valuations of items in the subset. For example, a customer of an online auction might want to purchase a CD player and an amplifier. Both items complement each other. Participating in separate auctions leaves her with the risk to win only one of the two items, a combinatorial auction can omit this.
The lecture investigates combinatorial auctions from an economic and a combinatorial optimization perspective. It describes the economic properties of the Vickrey-Clarke-Groves mechanism, and the combinatorial optimization problems that have to be solved in order to make this mechanism applicable in practice. It shows how a class of primal-dual algorithms for set packing relates to combinatorial auction design. For the special case of single-item auctions, it is shown that primal-dual algorithms define computationally efficient auctions that fulfill at the same time nice economic properties. The lecture is based on joined work with Andreas S. Schulz.
Colloquium - 16 Uhr s.t.
Abstract: Wir betrachten das ressourcenbeschränkte Projektscheduling-Problem. Dabei soll eine Menge von Jobs unter Berücksichtigung von Reihefolgebeziehungen und Ressourcenbeschränkungen eingeplant werden, so dass eine gegebene Zielfunktion optimiert wird. Es wird ein IP untersucht, mit dem partielle Ordnungen auf der Menge der Jobs beschrieben werden. Ziel ist es, solche partiellen Ordnungen zu finden, die in einer gewissen Weise zu Schedules mit maximaler Parallelität führen. Hierbei interessiert vor allem, wie gut die Lösungen des IP's und seiner LP-Relaxierung bezüglich der im Projektscheduling üblichen Zielfunktion der Projektdauerminimierung (Makespanminimierung) sind. Darüber hinaus soll auch geklärt werden, ob die verwendete IP-Formulierung zur Optimierung anderer Zielfunktionen geeignet ist. Ein vielversprechender Kandidat ist hierbei das ressourcenbeschränkte Projektplanungsproblem bei reihenfolgeabhängigen Setup-Kosten.