Strong Algorithms

Using approximation, online, and distributed algorithms, Dr. Dror Rawitz is attempting to solve problems related to computer systems

As a member of the Computer Engineering group at Bar-Ilan’s Faculty of Engineering, Dr. Dror Rawitz specializes in algorithms, and in particular in approximation, online, and distributed algorithms. “An algorithm is a finite sequence of actions that need to be carried out in order to solve a problem. A cake receipt is also an algorithm,” says Rawitz. “There are computationally hard optimization problems requiring efficient algorithms. In an optimization problem, one needs a solution whose cost or duration is minimized, or whose profit is maximized. For instance, we may need to design a work schedule for machines in a factory with the objective of completing all tasks at the least amount of time. There are natural optimization problems that are computationally hard, and the question of the existence of an efficient algorithm that solves them is a major open question. Approximation algorithms are algorithms that compromise on the quality of the computed solution, i.e., such an algorithm is an efficient algorithm that computes a solution that is close to optimal.”

Rawitz studies problems that arise in computer communication networks, such as maximizing network traffic or minimizing network design costs. In the past four years, Rawitz has been working on a research as part of the Neptune Consortium (the Israeli consortium for network programming) funded by the Israel Chief Scientist at the Ministry of Finances. The consortium’s members are hi tech companies and teams from academia. “Computer communication networks are in constant need of expansion to cope with the ever growing traffic.  As networks grow, management and maintenance become more and more complicated,” explains Rawitz. “Recently, there have been developments aiming to improve network utilization: the detachment of network applications from network infrastructure and the transition from network planning to network programming. Until recently, networks worked in a static manner, and network applications were located on fixed servers. Today things have become more dynamic and applications can be moved from one server to another. For example, if during nighttime a certain area is inactive, then servers can be shut down and activity can be gathered into a single server, to preserve energy. This allows for more flexibility, but needs to be managed. As part of the Neptune Consortium, my goal was to design algorithms that allocate traffic requests that include activation of several network applications. Part of this study was presented at the ALGOCLOUD 2017 conference.”

In addition, Rawitz also deals with problems in which the input arrives piece-by-piece, and an algorithm must make irreparable decisions without knowing the future. Such an algorithm is can an Online Algorithm. For instance, in the “paging problem”, the input is a sequence of accesses to blocks in the main memory, and the replacement protocol of a cache must decide which block to evacuate from the cache without knowing what will be the future accesses to the main memory. Like in approximation algorithms, the goal is to design an algorithm that finds a solution whose value is as close as possible to the optimum. Rawitz and his colleagues recently studied a generalization of the paging problem that includes applications such as working groups, compression, and changing of the cache size. Their study was presented at the SPAA 2018 conference.

Another problem Rawitz focuses on is the ‘Ski Rental problem’: “Assume that we are going on a ski vacation. We can rent the ski equipment on a daily fee or buy it for a one-time cost. The question is do we rent or buy? It’s an easy question if we know how long the trip will be, but what if we don’t? The problem could be made more complex by allowing an additional option of a club membership, which also costs, but not as much as buying the equipment, and lowers rental rates. In this case, the question is when to transition from one rental state to the next without knowing how long the trip will be,” explains Rawitz. “One possible application of this problem is transitioning from active/sleep modes on the computer. For example, if we’ve stop tapping on the keyboard, when would be the best time to go into sleep mode? On the one hand, if the computer is in sleep mode, it needs to save its status, turn itself off and then on again. This is a one-time waste of a lot of energy. Remaining active also requires energy, and this means lower energy waste per time unit during some time interval. The question is when it is best to go into sleep mode. This problem may sound very simple, but there are dozens of articles dealing with this problem and its variants. In an article published in the SIAM Journal of Discrete Mathematics in 2012, we studied the version of the problem in which there are several sleep modes. One of my student’s thesis also deals with this variant.”