Oblivious algorithms for the maximum directed cut problem

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

Shlomo Jozeph, Uriel Feige

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

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