How could two banks be merged efficiently? Which offices should close and which not? Where should people build new energy plants? To answer these kinds of questions Jarek Byrka (CWI) studied mathematical approximation techniques.
He defended his PhD thesis - Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria' - at the Technical University Eindhoven on Monday 13 October.
Better positioning of facilities feasible with mathematics
The trade-off between costs for building new facilities and servicing clients at a certain distance is difficult. In mathematical terms this facility problem is called ‘NP-complete'. For this kind of problems no efficient algorithms are known. Researchers even believe that they do not exist. Byrka designed an approximation technique and proved that his method can bring town planners closer to the optimal solution than before. This could considerably economize large building projects.
Byrka also studied problems in the field of Nash equilibria - a topic in game theory. In a Nash equilibrium a player cannot benefit by changing his or her strategy while the other players keep theirs unchanged. Computer scientists and economists are debating whether the market or a computer program is better in determining the location of a Nash equilibrium. Byrka studied this problem with constant factor approximations.
