8

I don't think the monotonicity will help much, for the following reason. Start with any arbitrary assignment problem. Add a constant amount $K$ to $c_{i2}$ for all $i$, with $K$ sufficiently large to make $c_{i2} > c_{i1}$ for all $i$. Since someone has to be assigned to sink 2, this effectively adds a constant amount $K$ to the objective function, and so ...


6

Yes. The ruggedness of a landscape is a measure of how much variability is observed between neighbouring solutions, and it can be computed using the landscape correlation function. Rugged landscapes (with a very low correlation) typically have lots of local minima and are more difficult to traverse than smooth landscapes (correlation close to 1). For a fixed ...


3

Minimizing the sum of all assignments: this is the classical version of the assignment problem. The Hungarian algorithm solves it in polynomial time. Minimizing the maximum of all assignments: this one is known as the linear bottleneck assignment problem. The most obvious way to solve it is to solve a succession a decision problems: is it possible to find ...


Only top voted, non community-wiki answers of a minimum length are eligible