Harnessing the Power of Local Search in Optimization and Game Theory


Wijzig gegevens

Titel Harnessing the Power of Local Search in Optimization and Game Theory
Looptijd 04 / 2010 - 01 / 2014
Status Lopend
Onderzoeknummer OND1337355
Leverancier gegevens NWO

Samenvatting (EN)

Logistics decisions often result in large-scale optimization problems, and finding good solutions to these problems is a key issue for improving economic performance. The most successful algorithms for many well-studied problems are based on the seemingly ad hoc principle of local search: start with an arbitrary feasible solution and perform some kind of local improvements until none is possible anymore. Even though local search heuristics are often the method of choice in practice, most of them behave poorly on (artificial) worst-case instances. The goal of this project is to develop a novel theory of local search that is not based on the pessimistic worst-case perspective. This will reconcile theory and practice and ultimately lead to improved heuristics with better practical performance. As real-world data is usually inherently noisy, it is realistic to circumvent the worst case by analyzing the behavior of heuristics on instances that are subject to a small amount of random noise. This approach, called smoothed analysis, led already to some remarkable results explaining the good practical behavior of various heuristics. The smoothed analysis of local search is, however, still in its infancy. Developing a solid understanding of local search is also important because of its close relation to algorithmic game theory, which studies how selfish agents behave in large decentralized networks (e.g., how bidders behave in ad auctions used by search engines to display advertisement). A key concept are Nash equilibria, i.e., states in which no agent has an incentive to deviate from his current strategy (e.g., his current bid). Nash equilibria are conceptually just local optima. Hence, our results will also yield new insights into some important problems from algorithmic game theory, e.g., why ad auctions are successful despite their bad worst-case properties. Keywords: Combinatorial Optimization, Analysis of Algorithms, Probabilistic Analysis, Local Search, Algorithmic Game Theory

Betrokken organisaties

Betrokken personen

Projectleider Dr. H. Röglin

Ga terug naar de inhoud
Ga terug naar de site navigatie