`Name:`

Set Cover `Domain:`

Optimization algorithms `Functionality:`

Solving the so-called set cover problem,which is also named key-lock problem. `Input:`

M:An $p \times q$ matrix ,where an element $m_{i,j}$ of M is either 0 or 1, and $m_{i,j} = 1$ denotes that the ith key can open the jth lock(Type: Matrix)

`Output:`

C: An integer(Type: Integer) $K(k_{1},k_{2},\cdots,k_C)$: An array, where K contains C keys that can open all keys(Type: Array)

`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Adding a column of “1” at the left of $M_s$, which means a lock that can be opened by all keys.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Changing the row order of $M_s$ between any pair of adjacent selected keys.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

The element $m^f_{i,j}$ of $M_f$ = 1 - the element $m^s_{(p-i+1),j}$of $M_s$`Output relation:`

$K_f = (k^f_{1},k^f_{2}, \cdots ,k^f_{C_f})$
$K_s = (k^s_{1},k^s_{2}, \cdots ,k^s_{C_s})$
$k^f_{1} \ne p - k_{1} + 1$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K$ `Input relation:`

$M_f$ = The first $C_s$ rows are the same as the $k_{1}th$,$k_{2}th$, \cdots ,$k_{C_s}th$ rows of $M_s$, and the remaining $p-C_s$ rows stores the data corresponding to unselected keys.
`Output relation:`

$C_f = C_s$
$K = (1,2,\cdots ,C_s)$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Deleting one useless row of $M_s$, which means unselected keys.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Adding a row of “0” at the bottom of $M_s$, which means a key that cannot open any lock.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Adding a row that is the subset of one existing row at the bottom of $M_s$, which means a key whose opened locks are the subset of those of one existing key.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Deleting the jth column whose $m_{i_{1},j} = 0$ from $M_s$, which means a lock that cannot be opened by the first selected key.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Adding a row that is the same as one existing row at the bottom of $M_s$,which means a key that is the same as one existing key.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Deleting the first row and all columns whose first element value is “1” of $M_s$, which means deleting the first key and all the locks that it can open.
`Output relation:`

$C_f = C_s -1$
$K_f = ( k^f_{1},k^f_{2},\cdots,k^f_{C_f})$, where $k^f_l = k^s_{l+1}$ if $k^s_{l+1}<k^s_{1}$ or $k^f_l = k^s_{l+1} -1$ if $k^s_{l+1}>k^s_{1}$.
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Adding some columns whose first element value is “1” and the other values are all “0”, which means adding some locks that can only be opened by the first key.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M^f_{2p \times q}$, where $m^f_{i,j} = m^s_{i,j}$and $m^f_{(p+i),j}= m^s_{i,j}$
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ = Changing the order of columns of $M_s$.
`Output relation:`

$C_f = C_s$
$K_f = K_s$
`Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ is a new $(p+a) \times q$ (a is a positive integer) matrix, whose first p rows are identical to $M_s$.
`Output relation:`

The number of locks that can be opened by $k^f_{1}$ is larger or equal to that of $k^s_{1}$. `Source input:`

$M_s$ ;
`Source output:`

$C_s,K_s$ `Follow-up input:`

$M_f$ ;
`Follow-up output:`

$C_f,K_f$ `Input relation:`

$M_f$ is a new $(p+a) \times (q+a)$ (a is a positive integer) matrix , the top-left $p \times q$ part is identical to $M_s$, the right-bottom $a \times a$ part is identical to a $a \times a$ unit matrix,and all the element in other parts are zero.
`Output relation:`

$C_f = C_s + a$
$K_f = {k^s_{1},k^s_{2},\cdots,k^s_{C_s},p+1,p+2,\cdots,p+a}$