skm_minmax_cpp {skm}

skm_minmax_cpp

Description

skm via min-max on in cpp - subroutine of skm_sgl_cpp calls

Usage

skm_minmax_cpp(x, s_must)

Arguments

x

an m x n matrix often m > n

s_must

matrix x row index start from 0 that must be selected with priority

Details

skm_minmax_cpp init an input m x n matrix x, and a priority vector s_must would select n indicies from m such that:

minimize sum(min(x(i, j) where i <1..n> and j <1..n> each use <1..n> once))

so in case m <= n it simply select all m - should always be apply on matrix with m > n - it is designed as a expectation step in skm_cpp on updating s.

it select i in <1..m> such that i has the colwise_min_idx on column j where j has max difference of (colwise_max_val - colwise_min_val), it then remove row i col j from matrix and repeat.

s_must presents the indices with priority so that the selection must select first indicies within s_must and then select other indicies outside s_must.

an example skm_minmax_cpp is superior in bound worst case compare to greedy: x = [1 100; 4 200; 2 400; 9 900]: greedy 1 then 200, min-max 100 then 2, and greedy give [1 100; 4 200] with 201 and minmax give [1 100; 2 400] with 102.