Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
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
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
2012. Vol. 24, no 1, 52-64 p.
Keyword [en]
APPROXIMATION
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-58603DOI: 10.1007/s10878-010-9318-6ISI: 000304400600004OAI: oai:DiVA.org:kth-58603DiVA: diva2:473412
Note

QC 20130204

Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lampis, Michael
By organisation
Theoretical Computer Science, TCS
In the same journal
Journal of combinatorial optimization
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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