Online Maximum Directed Cut
2009 (English)In: ALGORITHMS AND COMPUTATION, PROCEEDINGS / [ed] Dong, Y; Du, DZ; Ibarra, O, 2009, 1124-1133 p.Conference paper (Refereed)
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 3 root 3/2 approximate to 2.5981. We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of 3 root 3/2 - epsilon for any epsilon > 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.
Place, publisher, year, edition, pages
2009. 1124-1133 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5878
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-58585DOI: 10.1007/978-3-642-10631-6_113ISI: 000280382600111ISBN: 978-3-642-10630-9OAI: oai:DiVA.org:kth-58585DiVA: diva2:473386
20th International Symposium on Algorithms and Computations
QC 201201172012-01-052012-01-052012-01-17Bibliographically approved