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.
- SAT01 solver: An NP-complete problem solver with sample
converters for factoring problem. No, it's not another P=NP attempt, but a handy formulation to convert
NP-complete problems meant to replace CNF SAT.
- 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.)
Chess
I am a US National Master in chess.
This website is intentionally maintained in Web 1.0 form because the default HTML look is pretty enough and scripts
create more problems than solutions.
Stas Busygin <busygin@gmail.com>
Last update 11/29/2019