On the directed cut cone and polytope

DOI10.1007/s10878-015-9863-0zbMath1368.90135OpenAlexW2020537703MaRDI QIDQ281821

Conor Meagher, David Avis

Publication date: 11 May 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9863-0

zbMATH Keywords

combinatorial optimizationcut polytopedirected cut polytope

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Generalized cut and metric polytopes of graphs and simplicial complexes

Cites Work

• Unnamed Item
• Disjunctive programming: Properties of the convex hull of feasible points
• An application of branch and cut to open pit mine scheduling
• Quasi-semi-metrics, oriented multi-cuts and related polyhedra
• On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency
• Solving LP Relaxations of Large-Scale Precedence Constrained Problems
• Directed metrics and directed graph partitioning problems
• The Equivalent Subgraph and Directed Cut Polyhedra on Series-Parallel Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Reducibility among Combinatorial Problems
• Geometry of cuts and metrics