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.
Sergiy Butenko is a Professor in Wm. Michael Barnes '64 Department of Industrial and Systems Engineering at Texas A&M University. He also serves as the Editor-in-Chief of Journal of Global Optimization. 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 research focuses on discrete and global optimization, network analysis and network-based data mining, and graph theory. Applications of interest include biological, social, and financial networks, wireless ad hoc and sensor networks, transportation, and energy systems