Darren Strash, assistant professor of computer science, and his colleagues (Demian Hespe, Sebastian Lamm of Karlsruhe Institute of Technology, and Christian Schulz of University of Vienna) have been declared the winners of the Vertex Cover Track of the 4th Annual PACE Challenge — an annual research and programming competition with international recognition.
The PACE (Parameterized Algorithms and Computational Experiments) Challenge is an annual international competition begun in 2015 to “bridge the divide between the theory of algorithm design and analysis, and the practice of algorithm engineering.” Every year, new challenge problems are chosen and researchers from around the world vie to solve their problem on the most data sets in the shortest amount of time. This year, 18 teams competed to solve the Vertex Cover Problem (Track 1a of the 3-track challenge).
Before the contest deadline, teams were given 100 data sets for testing and developing their solvers, and the final winner was determined by the performance on 100 private instances. The entry by Strash and colleagues (named “WeGotYouCovered”), solved 87 out of 100 instances within the time limit set by the contest, which was 10 more than the second place solver.
WeGotYouCovered uses a “portfolio approach,” employing a collection of powerful techniques from the vertex cover literature in a 5-stage algorithm that is tuned to perform well on many data sets. One insight contributing to the solver’s success is that it uses a state-of-the-art techniques developed for other problems, including algorithms for the complementary Maximum Independent Set and Maximum Clique Problems. Research in these areas is fragmented, and the solver successfully brings them together.
As a result of their solver’s performance, the team was invited to present a poster and give a talk at the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) in Munich, Germany and were awarded a cash prize.
