טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentSchwartz Roy
SubjectCircular Arrangements
DepartmentDepartment of Computer Science
Supervisor Professor Joseph Naor


Abstract

We consider in this work the directed circular arrangement problem. The input is a directed graph with weights on the edges. The goal is to embed the graph onto evenly-spaced points on a circle, such that all edges are oriented in the same direction, say, clockwise, and the weighted sum of the lengths of the edges is minimized. The length of an edge is defined to be the (clockwise) distance between its two endpoints in the embedding. We note that each vertex is embedded onto a distinct point.

Our main result is an O(logn loglogn)-approximation algorithm for the directed circular arrangement problem. We obtain this result by defining a new problem, the directed penalized linear arrangement problem, and use a solution to this newly defined problem to approximate the directed circular arrangement. The directed penalized linear arrangement problem takes as input a directed graph and embeds it onto evenly spaced points on a straight line. In the embedding, edges that are directed to the right contribute to the objective function a term which is proportional to their (weighted) length, while edges that are directed to the left contribute to the objective function a term which is only proportional to the weight of the edge. We think of the latter term as a penalty.

The main contribution of this work is an O(logn loglogn)-approximation algorithm for the directed penalized linear arrangement problem. Our solution uses two distinct directed metrics (``right" and ``left") which together yield a lower bound on the value of an optimal solution. In addition, we define a sequence of new directed spreading metrics that are used for applying the algorithm recursively on smaller subgraphs. The directed penalized linear arrangement problem still shares some of the asymmetry characteristics of the directed circular arrangement problem. However, the new spreading metrics allow us to define an asymmetric region growing procedure that accounts simultaneously for both incoming and outgoing edges. To the best of our knowledge, this is the first work that defines a region growing

procedure in directed graphs that allows for such an accounting.