The expected relative error of the polyhedral approximation of the max-cut problem

The expected relative error of the polyhedral approximation of the max-cut problem

0.00 Avg rating—0 Votes
Article ID: iaor19961327
Country: Netherlands
Volume: 16
Issue: 4
Start Page Number: 191
End Page Number: 198
Publication Date: Nov 1994
Journal: Operations Research Letters
Authors: ,
Abstract:

The authors study the expected relative error of a linear relaxation of the max-cut problem in the random graph equ1. They prove that this error tends to equ2 as equ3 if the edge probability equ4 is at least equ5, and tends to 1 if equ6 and equ7 for all equ8.

Reviews

Required fields are marked *. Your email address will not be published.