Max-Cut Under Graph Constraints

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

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