T-shirt, casual pants, a pair of Birkenstocks, a knowledgeable smile, a subdued voice and unassuming. Gerhard Woeginger, a great mind, a compendium of knowledge of discrete algorithms and complexity, a source of inspiration to many colleagues and students for more than thirty years, has passed away.

Born on May 31, 1964 in Graz, Austria, Gerhard studied applied mathematics at Graz University of Technology. In 1991, he finished his PhD thesis under the supervision of Franz Rendl (Woeginger, 1991). He was on the faculty in Graz from 1991 to 2001 and completed his habilitation in 1995, after which he spent a year as postdoc at Eindhoven University of Technology. He returned to the Netherlands as a full professor at the University of Twente in 2001, moved to Eindhoven in 2004, and accepted the chair of algorithms and complexity at RWTH Aachen University in Germany in 2016. After a nine-month battle with cancer, he died on April 1, 2022.

It is not so easy to summarize his scientific work. His territory was vast, and he knew it well. He was interested in all sorts of problems and in algorithms of all flavors, be they exact, approximate, or online. He knew results from faraway times that had appeared in obscure journals, and he had an amazing talent to see connections across fields. Computational geometry, scheduling, social choice, bibliometrics and, of course, computational complexity, one of his prime loves. His drive to draw the line between easy and hard was infectious. He set up and maintained the P-versus-NP page, a vintage Gerhard-style webpage that collects attempts to settle this Millennium Prize Problem (Woeginger, 2016).

figure a

Among his many contributions, we mention his papers on approximation algorithms for scheduling parallel machines (Alon et al., 1998; Hoogeveen et al., 2001, 2003; Skutella & Woeginger, 2000; Woeginger, 1997), on the connection between dynamic programming and the existence of a fully polynomial-time approximation scheme (Woeginger, 2000), and on an axiomatic characterization of the h-index and other bibliometric indices (Woeginger, 2008a, 2008b, 2009). As a byproduct of the latter analysis, he invented the w-index, which has favorable properties; however, promoting it was not in his nature. He wrote a number of authoritative surveys on subjects like well-solvable cases of the traveling salesman problem (Burkard et al., 1998), online algorithms (Csirik et al., 1998), and exact algorithms for NP-hard problems (Woeginger et al., 2003).

He published more than 400 papers, about eighty of which are on scheduling. His paper on ten notorious open problems related to the approximability of machine scheduling problems, published in the Journal of Scheduling in 1999 (Schuurman & Woeginger, 1999), became quite influential. Several of these problems have been settled by now, be it through better lower bounds, e.g., based on the unique games conjecture, or through better upper bounds, using new relaxations or new rounding techniques. It is remarkable that all progress made on these ten problems has been nontrivial, which testifies to their significance.

Gerhard’s work did not go unnoticed by funding agencies and prize committees. He was the recipient of the Austrian Start-Preis in 1996, of a Dutch NWO Vici grant in 2004, and of a German Humboldt Research Award in 2011. He was on the program committee of an enormous number of conferences, he was program chair of ESA 1997, MAPSP 2005, EURO 2009 and IPCO 2011, and he was on the board of a dozen journals, including the Journal of Scheduling.

Gerhard’s curiosity was authentic, and he could listen. He was open toward newcomers in the community, and he was able to find truth in one’s unstructured words. Among German colleagues, when an argument was basically clear while the details had not yet been worked out, he would say: “Das geht sich dann aus”—“that will do.” He had an uncanny ability to distill the essentials of an argument and write it down in a natural and elegant way.

He was a teacher with a natural gift. Many of us have attended his tantalizing talks. He could make complicated proofs look simple. He would then show his mysterious smile, which expressed a mixture of modesty and mastery, sometimes perhaps with a hint of mockery. Once, during a talk, Gerhard used Lenstra’s polynomial algorithm for integer programming with a fixed number of variables (Lenstra, 1983). After the talk, Jan Karel suggested that next time he should perhaps mention the first name of this Lenstra: “Otherwise they think it’s me.” When Gerhard gave the talk again and invoked Lenstra’s algorithm, he turned around, pointed to Jan Karel, and said: “Not him.”

During the many workshops that he visited, he liked to socialize with friends. Science was never far away. Gerhard knew about the ideal composition of a darts board. He introduced the Mafia social game to several communities and played it with passion until early in the morning. He could even get upset when players made unreasonable decisions. Without Gerhard, Mafia will not be the same. However, after he had recovered from a bike accident in Eindhoven in 2007, we saw less of him at meetings.

Frits had dinner with Gerhard in Aachen on March 23. “I feel guilty about something I did in Eindhoven,” Gerhard said. “When they were cleaning out the library, I found Duijvestijn’s PhD thesis from 1962 (Duijvestijn, 1962). His perfect square is still on the cover of the Journal of Combinatorial Theory. I took the thesis. Actually, I have it with me now.” “Do you want me to return it to Eindhoven?” Frits asked. “Yes, I do,” he said.

Gerhard will be missed for so much and for so many little things. Our field has lost a formidable scientist, we have lost a dear friend. Rest in peace, Gerhard.