Relaxations of combinatorial problems via association schemes

DOI10.1007/978-1-4614-0769-0_7zbMATH Open1334.90100OpenAlexW2158270219WikidataQ56874365 ScholiaQ56874365MaRDI QIDQ2802525FDOQ2802525

E. de Klerk, Dmitrii V. Pasechnik, Fernando M. de Oliveira Filho

Publication date: 26 April 2016

Published in: International Series in Operations Research & Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-0769-0_7

Recommendations

• SDP relaxations for some combinatorial optimization problems
• scientific article; zbMATH DE number 1944141
• scientific article; zbMATH DE number 1873286
• Matrix relaxations in combinatorial optimization
• Semidefinite relaxations for partitioning, assignment and ordering problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Shannon capacity of a graph
• Approximation algorithms for maximization problems arising in graph partitioning
• Title not available (Why is that?)
• A General Approximation Technique for Constrained Forest Problems
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Minimum-weight cycle covers and their approximability
• Semidefinite programming relaxations for the quadratic assignment problem
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• A comparison of the Delsarte and Lovász bounds
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A .699-approximation algorithm for Max-Bisection.
• Semidefinite programming and integer programming
• Multilinear algebra. 2nd ed
• An improved rounding method and semidefinite programming relaxation for graph partition
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Commutative association schemes
• Title not available (Why is that?)
• A GAP Package for Computation with Coherent Configurations

Cited In (14)

• An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
• Graph bisection revisited
• Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
• Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
• Semidefinite programs and association schemes
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• Gaddum's test for symmetric cones
• On semidefinite programming bounds for graph bandwidth
• Minimum energy configurations on a toric lattice as a quadratic assignment problem
• The independence number for polarity graphs of even order planes
• Symmetry in Turán sums of squares polynomials from flag algebras
• The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• On Integrality in Semidefinite Programming for Discrete Optimization

Uses Software

• GAP
• Cohcfg

This page was built for publication: Relaxations of combinatorial problems via association schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802525)