Abstract
We investigate a natural online version of the well-known Maximum Directed Cut problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of \(\frac{3\sqrt{3}}{2}\approx 2.5981\). We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of \(\frac{3\sqrt{3}}{2}-\epsilon\) for any ε> 0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MaxDiCut in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Spencer, J.: The Probabilistic Method. Wiley-Interscience, Hoboken (2004)
Bazgan, C., Tuza, Z.: Combinatorial 5/6-approximation of max cut in graphs of maximum degree 3. J. Discrete Algorithms 6(3), 510–519 (2008)
Feige, U., Goemans, M.: Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT. In: Proceedings of the Third Israel Symposium on the Theory of Computing and Systems, 1995, pp. 182–189 (1995)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Hadlock, F.: Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM Journal on Computing 4, 221 (1975)
Halperin, E., Zwick, U.: Combinatorial approximation algorithms for the max- imum directed cut problem. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, PA, USA, pp. 1–7. Society for Industrial and Applied Mathematics Philadelphia (2001)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, Newyork (1972)
Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability re-sults for MAX-CUT and other 2-variable CSPs? In: Proceedings. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 146–154 (2004)
Lampis, M., Kaouri, G., Mitsou, V.: On the algorithmic effectiveness of di-graph decompositions and complexity measures. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 220–231. Springer, Heidelberg (2008)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and com-plexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Noy, A., Lampis, M. (2009). Online Maximum Directed Cut. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_113
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_113
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)