1
$\begingroup$

For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a?

Sorry if this is super trivial, I did not find an answer

e.g here: No Small Linear Program Approximates Vertex Cover Within a Factor 2 − $ \epsilon $ pg 16 x does not extend \alpha

$\endgroup$
3
$\begingroup$

It means that you have a partial solution, and you extend that partial solution by assigning at least one more variable to some value, thus producing either a new partial solution or a solution where every variable is assigned a value.

Put differently, if $x$ extends an assignment $a$, it holds that $x$ does precisely the same assignments as $a$ and assigns any number of other variables in addition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.