DR. SERGIY BUTENKO
Professor, Donna and Jim Furber `64 Faculty Fellow
Department of Industrial and Systems Engineering
Texas A&M University
Date: Friday, Feb 28, 2020
Time: 1 - 1:50 pm
Location: D3 W122
Abstract: The celebrated Motzkin-Straus formulation of the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turan's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such as s-defective clique and s-plex, emerged as attractive, more practical, alternatives to cliques in network-based cluster detection models arising in numerous applications. This talk presents continuous cubic formulations for the maximum s-defective clique and the maximum s-plex problems by generalizing the Motzkin-Straus formulation to the corresponding clique relaxations. The formulations are used to extend the Turan's theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments demonstrate that the proposed formulations can be used to quickly compute large clusters of interest. The talk is based on a joint work with Vladimir Stozhkov, Austin Buchanan, and Vladimir Boginski.
Biography: Sergiy Butenko is a Professor and Donna and Jim Furber `64 Faculty Fellow in Industrial and Systems Engineering at Texas A&M University. He received his B.S. and M.S. degrees in Mathematics at Kyiv National Taras Shevchenko University (Ukraine) and M.S. and Ph.D. degrees in Industrial and Systems Engineering at the University of Florida. His work has been supported by the Air Force office of Scientific Research (including the 2009 Young Investigator Program award), the U.S. Department of Energy, the National Science Foundation, Office of Naval Research, and NATO. He is the editor in chief of Journal of Global Optimization and a member of editorial boards of several other journals and book series.