Approximation algorithms
largest practical instances. Jochen explains: “IBM is using my algorithm to manufacture some of its chips. In chip design, flow problems naturally arise in the layout process. How do we place components on the chip and how do we connect these components to each other using wires? Those problems are often too large to be solved exactly. So the solution my algorithm returns is a few percent off the optimal, but it’s good enough.”
Approximation algorithms also have applications in network and game theory. Connecting network points to each other by the shortest length, allowing the addition of extra points, is called the ‘Steiner tree problem’. This classical optimization problem is the foundation for Jochen’s work on network design. In game theory, ‘players’ choose actions in an attempt to maximize their return. Jochen explores the connections between game theory and combinatorial optimization, looking for ways to apply algorithmic game theory to classical (Steiner tree) and practical (online auctions) problems.