In memoriam: Gerhard Woeginger


He was unassuming. He was nice. He could think. He could write. And he knew a lot. He died last Friday, April 1, 2022. His name was Gerhard Woeginger, a prolific computer scientist.


Some facts of his life and career can be easily summarized as follows. Born on May 31, 1964 in Graz, he studied at the Graz University of Technology, and got a PhD under Franz Rendl in 1991 with a thesis entitled "Geometric clustering, Reconstruction and Embedding Problems: Combinatorial Properties and Algorithms". He became a professor at the University of Twente (the Netherlands) in 2001, and joined TU/e as a professor in 2004. In 2016 he moved to RWTH Aachen. During his time at TU/e, he supervised around 10 PhD-students. 


Describing the impact of his career on the field is not so easily summarized. He was present in almost every field within theoretical computer science. Social choice, bibliometrics, algorithms (especially online), approximability, computational geometry, and of course, one of his prime loves: computational complexity. His talent to see connections between different problems was amazing. His ability to distill the essentials, and then write it up in a way that it all seemed natural was uncanny. And his drive and enthusiasm to distinguish easy from hard, was absolutely infectious. The math and computer science department of TU/e, as well as the NETWORKS community, owes him a lot - we are very grateful for his time spent here. His friendliness combined with a deep mathematical curiosity has been a source of inspiration for all around him. 


He was on the program committee of an enormous number of conferences, he was program chair of ESA1997, MAPSP2005, IPCO2011, EURO2009, and he was on the board of a dozen journals among which OR Letters. He set up, and maintained the P-versus-NP page, a vintage Gerhard-style set of webpages that discusses attempts to settle the P=NP question. To say that he contributed to the Christmas puzzle (Advents Kalender) is an understatement, he single-handedly ensured the existence of it. And there is much, much more to be said.


Above all, he could listen - he was able to identify truth in one's unstructured words. And then he'd write the paper, faster than one thought was possible. We will miss his presence at conferences, his revealing questions at presentations, his modest smile when the result was discovered, and his knowledge. He knew about the origins of the term NP-complete, he knew results from faraway times in obscure journals; he also knew about the ideal composition of a darts board, and he knew his soccer.


I am going to close with a personal anecdote. I visited Gerhard in Aachen, where we had dinner. He said "I feel a bit guilty about something I did while at TU/e - I stole something". I said: "Well, as TU/e is still standing, it can't have been too bad - what did you take?". "When they were cleaning out the library many years ago, I found a copy of a PhD thesis from 1962, written by Duyvesteyn. In it, Duyvesteyn finds a partition of a square into smaller squares. The corresponding picture is still on the cover of the Journal of Combinatorial Theory. I took the book with me, and actually, I have the book with me now. I want you to return it to TU/e." "Are you sure?" I asked. "Yes, I am sure." he said.


Frits Spieksma