Online maximum directed cut

DOI10.1007/s10878-010-9318-6zbMath1254.90270OpenAlexW2086937655MaRDI QIDQ454250

Michael Lampis, Amotz Bar-Noy

Publication date: 1 October 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9318-6

zbMATH Keywords

online algorithmsDAGM\textsc{ax}D\textsc{i}C\textsc{ut}

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (6)

Intersection properties of maximal directed cuts in digraphs ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Optimization with uniform size queries ⋮ Online Submodular Maximization with Preemption ⋮ Oblivious algorithms for the maximum directed cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Optimization, approximation, and complexity classes
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Online maximum directed cut