Stas Busygin's Home Page

Selected writings

• A Least Squares Framework for the Maximum Weight Clique Problem, 2002-2007.
• A New Trust Region Technique for the Maximum Weight Clique Problem, Discrete Applied Mathematics 154(15) (International Symposium on Combinatorial Optimization CO'02), pp. 2080-2096, 2006.
• On NP-hardness of the clique partition -- independence number gap recognition and related problems, Discrete Mathematics 304(4), pp. 460-463, 2006 (with D.V. Pasechnik, see also ECCC Report TR03-052).
• The SAT01 framework for NP problems, 2003.
• A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics, 2002.

Software

• QUALEX-MS: QUick ALmost EXact Maximum Weight Clique/Independent Set Solver based on the Motzkin-Straus QP formulation. Here is 80 DIMACS graphs on which the algorithm was tested.
• theta-weighted-dimacs computes the (weighted) Lovasz number (theta function) of a graph given in the text or binary DIMACS format.
• JacMat: Jacobson-Matthews random Latin square generator.
• AntiSM: generator of graphs hard for greedy maximum clique heuristics (described in this paper.)
• VS: creates a vertex-saturated digraph from a given undirected graph.