Dear All!
In this message I would like to disavow one claim appeared
recently in a SIAM paper of three highly respected
researchers. Namely, A. Massaro, M. Pelillo, and I. M. Bomze
in "A Complementary Pivoting Approach to the Maximum Weight
Clique Problem", SIAM J. Optim. Vol. 12, No. 4, pp. 928--948
wrote (p. 941):
> The latter fact shows the effectiveness of Brockington and
> Culberson's approach for producing hard problems for
> algorithms based on the Motzkin-Straus continuous
> formulaion.
To remind, Brockington and Culberson constructed a specific
graph generator hiding a maximum clique from easy disclosure
by all known that time solving techniques, and 12 their
instances (brock*) appeared in the DIMACS clique benchmarks
have been considered the tightest. Massaro et al. concluded
that those instances are hard for algorithms using the
Motzkin-Straus formulation on the basis of failure of few
related heuristics.
However, tractability of brock* instances was discovered in
2000 with appearance of QUALEX solver. In 2001 a more
efficient Motzkin-Straus based version of the algorithm was
developed, and the paper "A New Trust Region Technique for
Maximum Weight Clique Problem" dedicated to it was published
in the net in January 2002:
http://www.busygin.dp.ua/npc.html#stuff
http://www.optimization-online.org/DB_HTML/2002/01/430.html
The Massaro et al. paper was published electronically in
March 2002, though initially it was submitted in November
2000. So, due to the "promptness" of a respectable journal
the paper appeared significantly outdated. This aggravated
that initially negligent -- IMHO -- claim of the authors.
However, I am not going to blame anyone here. The goal of
this message is rather an appeal to people working on hard
problem algorithms to publish working notes in the net as
soon as a significant step is done. Personally I am going
to start a new note series on maximum clique problem in few
days in algorithm-forge group:
http://groups.yahoo.com/group/algorithm-forge
It should be finalized after some time with appearance of
the next QUALEX-MS version, possibly ALways EXact.
Together we shall make the progress on hard computational
problems faster!!
Best regards,
Stas Busygin
email: [log in to unmask]
WWW: http://www.busygin.dp.ua
|