header

Set Cover : Solving the so-called set cover problem,which is also named key-lock problem.
Tag:
Edit edit   Starstar

Program Information

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)

Reference

     How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46

MR Information


MR1


    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$

MR2


    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$

MR3


    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$

MR4


    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)$

MR5


    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$

MR6


    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$

MR7


    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$

MR8


    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$

MR9


    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$

MR10


    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}$.

MR11


    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$

MR12


    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$

MR13


    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$

MR14


    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}$.

MR15


    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}$

Related

Insert title here