The max-cut problem is one ofthe well known and most studied hard optimization problems. In this paper we present an easily computable upper bound on the max-cut based on the maximum eigenvalue of an associated matrix. The connection between eigenvalues and cuts in graphs has been first discovered by Fiedler. The eigenvalue based methods have proved to be useful also for some other problems, e.g. expanding properties of graphs, isoperimetric numbers of graphs, etc.
Track: Operations Research
Published in: 9th Annual International Conference on Industrial Engineering and Operations Management, Bangkok, Thailand
Publisher: IEOM Society International
Date of Conference: March 5
-7
, 2019
ISBN: 978-1-5323-5948-4
ISSN/E-ISSN: 2169-8767