kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Online Maximum Directed Cut
2009 (English)In: ALGORITHMS AND COMPUTATION, PROCEEDINGS / [ed] Dong, Y; Du, DZ; Ibarra, O, 2009, p. 1124-1133Conference paper, Published paper (Refereed)
Abstract [en]

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. p. 1124-1133
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5878
Keywords [en]
APPROXIMATION
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-58585DOI: 10.1007/978-3-642-10631-6_113ISI: 000280382600111Scopus ID: 2-s2.0-75649126558ISBN: 978-3-642-10630-9 (print)OAI: oai:DiVA.org:kth-58585DiVA, id: diva2:473386
Conference
20th International Symposium on Algorithms and Computations
Note
QC 20120117Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2022-06-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lampis, Michael
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf