Online Maximum Directed Cut
2012 (English)In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 24, no 1, 52-64 p.Article in journal (Refereed) Published
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
2012. Vol. 24, no 1, 52-64 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-58603DOI: 10.1007/s10878-010-9318-6ISI: 000304400600004OAI: oai:DiVA.org:kth-58603DiVA: diva2:473412
QC 201302042012-01-052012-01-052013-02-04Bibliographically approved