Oblivious algorithms for the maximum directed cut problem
From MaRDI portal
Publication:2346965
DOI10.1007/s00453-013-9806-zzbMath1315.68279arXiv1010.0406OpenAlexW1514114782MaRDI QIDQ2346965
Publication date: 26 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.0406
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