------------------------------------------------------------------------
			      LSCS 2007
         Fourth International Workshop on
  Local Search Techniques in Constraint Satisfaction


			     REVIEW FORM
------------------------------------------------------------------------
Paper number: 5

Title: The Promise of Polynomial-based Local Search to Boost Boolean
MAX-CSP Solvers

Author: Christine D. Hang, Ahmed Abdelmeged, Daniel Rinehart, Karl
J. Lieberherr



EVALUATION CATEGORIES (little/some/much)

Relevance: much
Originality: much
Significance: some
Technical Quality: some
Clarity: little


OVERALL RANKING (1-5, 1 the lowest): 3

SHOULD BE PUBLISHED IN PROCEEDINGS (yes/no): 

DETAILED COMMENTS FOR THE AUTHORS (use as much space as you want):

The paper presents an interesting approach for finding promising
assignments to MAX-CSP instances. As far as I know this is a new
idea. For this reason I think the work deserves to be
presented. Nevertheless, there are some points in which the work can
be improved:

- Clarity: the paper is very difficult to read. The main reason is
that the general picture can be understood only at the end of the
paper, after having read many technicalities, of which meaning and
role are not immediately clear. I suggest to start the paper giving
the intuition of the technique and providing a clear path toward the
more formal parts. Of the same spirit is an observation I have about
figure 1: without any explanation, its meaning is quite low.

- Experimental analysis: for a future publication, I suggest to extend
section 7. Of course, more instances have to be considered. The
experimental setting should be defined carefully: a reader wants to
know not only the improvement upon the performance of the solver
without ELS, but also the total runtime. Moreover, a comparison
against state-of-the-art constructive procedures and stochastic local
search techniques should be done, both as 'preprocessors' and plain
solvers.

- Related and references: references on stochastic local search for
SAT/MAXSAT/MAX-CSP are not up-to-date. The main sources are probably
the book by Hoos and Stuetzle, Stochastic Local Search, Morgan
Kauffman, 2004 (see also references therein) and recent papers by Hoos
(et al.) and Selman (et al.).


Minor comments:

- the use of the term 'preprocessing' is misleading, as it suggest
that some characteristics or properties of the instance or of the
algorithm are processed, whilst it is only a matter of starting with a
good initial assignment.

- is there a strong requirement for having a provable good initial
assignment? What is the advantage over usual stochastic constructive
procedures?

========================================================================