Max-Cut Under Graph Constraints
From MaRDI portal
Publication:3186491
DOI10.1007/978-3-319-33461-5_5zbMath1419.90112arXiv1511.08152OpenAlexW2278134082MaRDI QIDQ3186491
Viswanath Nagarajan, Xiangkun Shen, Jon Lee
Publication date: 10 August 2016
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.08152
Related Items (7)
A maximum dicut in a digraph induced by a minimal dominating set ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Approximating graph-constrained max-cut ⋮ Parameterized complexity of multi-node hubs ⋮ Complexity of the max cut problem with the minimal domination constraint
Cites Work
- Unnamed Item
- 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
- 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
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- 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
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- 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: Max-Cut Under Graph Constraints
