liveBook · Manning

Independent zero

As explained in Algorithms Every Programmer Should Know

An independent zero is a zero matrix entry selected so that no other selected zero lies in the same row or column.

An independent zero is a zero in a cost matrix selected without choosing another zero from the same row or column. Together, independent zeroes represent assignments with no worker or task repeated. section 3.4

In the Hungarian algorithm, select independent zeroes after the matrix has enough covering lines, starting with rows or columns that contain only one zero. Use the resulting worker-task pairs to look up the original costs. section 3.1 section 3.4

Assigning cleaners to rooms

Alice is assigned to Floors, Bob to Kitchen, and Carol to Windows. Each worker and task appears once, so the assignments do not overlap. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines non-overlapping zero selection and gives a selection heuristic, without detailing implementation.
Examples
Illustrates distinct worker-task assignments with cleaners and rooms, and discusses developers assigned to software modules.
What you can do after
Apply independent zeroes to form worker-task pairs without repeating a row or column.
How it connects
Connects independent zeroes to the Hungarian algorithm and the linear sum assignment problem.

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.