Approximating graph-constrained max-cut
From MaRDI portal
Publication:1800989
DOI10.1007/s10107-017-1154-3zbMath1406.90106OpenAlexW2611730178MaRDI QIDQ1800989
Jon Lee, Viswanath Nagarajan, Xiangkun Shen
Publication date: 26 October 2018
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-017-1154-3
Related Items (2)
Computing the largest bond and the maximum connected cut of a graph ⋮ Approximating max-cut under graph-MSO constraints
Cites Work
- Unnamed Item
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Approximation algorithms for connected maximum cut and related problems
- Tree-width and the Sherali-Adams operator
- A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Max-Cut Under Graph Constraints
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- MaxMin allocation via degree lower-bounded arborescences
- Minimum Congestion Mapping in a Cloud
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Sparsest cut on bounded treewidth graphs
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
This page was built for publication: Approximating graph-constrained max-cut
