Oblivious algorithms for the maximum directed cut problem

DOI10.1007/s00453-013-9806-zzbMath1315.68279arXiv1010.0406OpenAlexW1514114782MaRDI QIDQ2346965

Shlomo Jozeph

Publication date: 26 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.0406

zbMATH Keywords

linear programminglocal algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Randomized algorithms (68W20)

Related Items (10)

Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Near-optimal asymmetric binary matrix partitions ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ A spectral partitioning algorithm for maximum directed cut problem ⋮ Online Submodular Maximization with Preemption

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online maximum directed cut
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• New local search approximation techniques for maximum generalized satisfiability problems
• Parallel approximation algorithms by positive linear programming
• Generalization of a theorem by v. Neumann concerning zero sum two person games
• Survey of local algorithms
• Towards Sharp Inapproximability for Any 2-CSP
• Maximizing Non-monotone Submodular Functions
• Maximum directed cuts in acyclic digraphs
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• AdWords and generalized online matching
• Survey on Oblivious Routing Strategies
• Maximum directed cuts in digraphs with degree restriction
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Online bipartite matching with random arrivals
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Automata, Languages and Programming

This page was built for publication: Oblivious algorithms for the maximum directed cut problem