Jochen Könemann

Approximation algorithms

Business often faces the need to make decisions with imperfect data and definite time and cost constraints. Jochen Könemann predominantly works on discrete optimization problems that are provably hard to solve exactly in short time. He creates approximation algorithms that trade off efficiency for time. He explains; “An approximation algorithm efficiently computes a feasible solution to the problem. The quality difference between the optimal solution and the approximate is small.” A large class of real-world optimization problems can be cast as network flow problems; roughly, the objective here is to optimize flow through a system (IT networks, pipelines, computer chips). Such problems can be modelled as so-called ‘packing linear programs’ and there are exact algorithms available that can handle small-to moderate sized instances. Jochen has developed approximation algorithms for these problems that allow for a fast approximate solution of even the

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.