header

SCP/ KLP : Finding the smallest subset of O(objects) that satisfies all requirements in R(requirements).
Tag:
Edit edit   Starstar

Program Information

Name: SCP/ KLP
Domain: Optimization algorithms
Functionality: Finding the smallest subset of O(objects) that satisfies all requirements in R(requirements).
Input:
     K($k_{1},k{2},\cdots,k_m$): A set of keys(Type: Set) L($l_{1},l_{2},\cdots,l_n$): A set of locks (Type: Set) R: The relationship between key $k_i$ and lock $l_j$(i=1,2,……m,j=1,2,……n), such that $r_{i,j}=1$ if $k_i$ opens $l_j$,and $r_{i,j}$=0,otherwise.(Type:Matrix)
Output:
     O: The smallest subset of a set of keys that opens all requirements in a set of locks (Type: Set)

Reference

     Testing of Heuristic Methods: A Case Study of Greedy Algorithm http://dx.doi.org/10.1007/978-3-642-22386-0_19

MR Information


MR1


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f = K_s$ $L_f = L_s$ $R_f$ = Interchanging the columns of $R_s$
    Output relation: $O_f$ = $O_s$

MR2


    Source input: $K_s(k_{1},k_{2},\cdots,k_m),L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f(k_{1},k_{2},\cdots,k_m,k_{m+1}),L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f = K_s+k_{m+1}$ $L_f = L_s$ $R_f$ = Adding a useless key row,is also a row of zero, at the bottom of the matrix $R_s$.A key said to be useless if it cannot open any locks.
    Output relation: $O_f$ = $O_s$

MR3


    Source input: $K_s,L_s(l_{1},l_{2},\cdots,l_n),R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f(l_{1},l_{2},\cdots,l_n,l_{n+1}),R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f = K_s$ $L_f = L_s + l_{n+1}$ $R_f$ = Adding an insecure lock column,is also a column of one, at the right of the matrix $R_s$.A lock is insecure if it can be opened by any key.
    Output relation: $O_f$ = $O_s$

MR4


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f = K_s$ $L_f = L_s$ $R_f$ = Rearranging rows of $R_s$ corresponding to the selected keys on top while preserving their order.
    Output relation: $O_f$ = $O_s$

MR5


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f$ = $K_s$ + a new Key x, x is a combination of the second and third keys of $O_s$. $L_f$ = $L_s$ + n new locks , y is the first key of $O_s$, n = NumOpenLocks(x) - NumOpenLocks(y), the n locks can be only opend by y. $R_f$ = $R_s$ + the numbers(0/1) that represent the relationship between keye and locks which are presented above.
    Output relation: $O_f$ - x = ($O_s$ - the second key of $O_s$) - the third key of $O_s$

MR6


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f$ = $K_s$ - a key x, x is a row in $K_s$ $L_f$ = $L_s$ - all locks that can be satisfied by the key x+ n new locks $R_f$ is obtained from $R_s$ by resetting the first key of $O_s$ so that it can only open those locks that can be opened by x (say x is $O_{[i]}$, $2 \le i \le numOs$) but not by any key y where y = $O_{[j]}$, $2 \le j < i$.
    Output relation: $O_f = O_s -x$

MR7


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f$ = $K_s$ - a key x, x is a row in $K_s$ $L_f$ = $L_s$ - all locks that can be satisfied by the key x+ n new locks, N is the number of locks that can be opened by both x and y,y is a selected key preceding x in $O_s$. $R_f$ is obtained from $R_s$ by deleting a selected key while preserving the order of the remaining selected keys.
    Output relation: $O_f = O_s -x$

MR8


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f$ = $K_s$ $L_f = L_f + L_s + l_{n+1}$ $R_f$ is obtained from $R_s$ by adding an extra column, is also an exclusive lock that corresponds to an exclusive lock to a particular unselected key.
    Output relation: $O_f$ = $O_s$ - some previously selected key + some new key

MR9


    Source input: $K_s, L_s,R_s$ ; Source output: $O_s$
    Follow-up input: $K_f,L_f,R_f$ ; Follow-up output: $O_f$
    Input relation: $K_f$ = $K_s$ $L_f = L_f + L_s + l_{n+1}$ $R_f$ is obtained from $R_s$ by adding an extra column that corresponds to an exclusive lock to a particular unselected key x and reset x so that it can open and only open that exclusive lock.
    Output relation: $O_f - x = O_s$

Related

Insert title here