The directed circular arrangement problem

ABSTRACT

We consider the problem of embedding a directed graph onto evenly-spaced points on a circle while minimizing the total weighted edge length. We present the first poly-logarithmic approximation factor algorithm for this problem which yields an approximation factor of O(log n log log n), thus improving the previous Õ(√n) approximation factor. In order to achieve this, we introduce a new problem which we call the directed penalized linear arrangement. This problem generalizes both the directed feedback edge set problem and the directed linear arrangement problem. We present an O(log n log log n) approximation factor algorithm for this newly defined 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 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 time that a region growing procedure is defined in directed graphs that allows for such an accounting.

REFERENCES

• 1: Amotz Bar-Noy , Joseph Naor , Baruch Schieber, Pushing dependent data in clients-providers-servers systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.222-230, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345950]
• 2: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 3: Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
• 4: G. Even, J. Naor, B. Schieber and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, Vol. 20 (1998) pp. 151--174.
• 5: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 6: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 7: Vincenzo Liberatore, Circular Arrangements, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.1054-1066, July 08-13, 2002
• 8: Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
• 9: P. Seymour, Packing Directed Circuits Fractionally, Combinatorica, No. 15, 1995, pp. 281--288.