Congratulations to CS students Gil Ben-Shachar (project supervisor), Yonatan Sommer, Jonathan Josef, Tomer Cohen, and Matan Mamistvalov, who came in honorable places in the NP-Complete Problem Solving Competition at the SoCG’21 Conference - the world's leading conference on computational geometry. The contest had two categories, and each had two tracks: A general track and a track for teams that included only students and no faculty members. The team of Yonatan and Jonathan reached the fourth and seventh places in the two categories (second and fourth among student teams), and the team of Tomer and Matan reached the eighth and fifth places (sixth and second among student teams). 30 teams attended the competition.

The project was carried out within the research group of Professor Gill Barequet. The purpose of the competition was to solve as efficiently as possible a huge collection of instances (from small to very large) of a problem known as an NP-Complete problem. This year, the competition dealt with the following problem: Given a set of robots on the square lattice, and a target square for each robot, compute an efficient path for each robot while taking into account the positions of the other robots and other fixed obstacles on the lattice.

Well done to Gil, Yonatan, Jonathan, Tomer, Matan, and Gill![Back to the news index]