`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)
Testing of Heuristic Methods: A Case Study of Greedy Algorithm http://dx.doi.org/10.1007/978-3-642-22386-0_19

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`

`Description:`

`Property:`

`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 `Pattern:`

`Description:`

`Property:`

`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$ `Pattern:`