Online maximum directed cut |
| |
Authors: | Amotz Bar-Noy Michael Lampis |
| |
Affiliation: | 1. Doctoral Program in Computer Science, Graduate Center, City University of New York, 365 5th Avenue, New York, NY, 10016, USA
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|