# 永利总站ylzz55|首頁|欢迎您

In this talk, we consider two types of robust models of the \$k\$-median/\$k\$-means problems: the outlier-version (\$k\$-MedO/\$k\$-MeaO) and the penalty-version (\$k\$-MedP /\$k\$-MeaP), in which we can mark some points as outliers and discard them. In \$k\$-MedO /\$k\$-MeaO, the number of outliers is bounded by a given integer. In \$k\$-MedO/\$k\$-MeaO, we do not bound the number of outliers, but each outlier will incur a penalty cost.  We develop a new technique to analyze the approximation ratio of local search algorithms for these two problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. For \$k\$-MeaP, we improve the best known approximation ratio based on local search from \$25+\veps\$ to \$9+\veps\$. For \$k\$-MedP, we obtain the best known approximation ratio. For \$k\$-MedO/\$k\$-MeaO, there exists only two bi-criteria approximation algorithms based on local search. One violates the outlier constraint (the constraint on the number of outliers), while the other violates the cardinality constraint (the constraint on the number of clusters). We consider the former algorithm and improve its approximation ratios from \$17+\veps\$ to \$3+\veps\$ for \$k\$-MedO, and from \$274+\veps\$ to \$9+\veps\$ for \$k\$-MeaO.  (Joint work with Yishui Wang, Rolf H. Mohring, Chenchen Wu, and Dongmei Zhang).

2020年12月1日

In this talk, we consider two types of robust models of the \$k\$-median/\$k\$-means problems: the outlier-version (\$k\$-MedO/\$k\$-MeaO) and the penalty-version (\$k\$-MedP /\$k\$-MeaP), in which we can mark some points as outliers and discard them. In \$k\$-MedO /\$k\$-MeaO, the number of outliers is bounded by a given integer. In \$k\$-MedO/\$k\$-MeaO, we do not bound the number of outliers, but each outlier will incur a penalty cost.  We develop a new technique to analyze the approximation ratio of local search algorithms for these two problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. For \$k\$-MeaP, we improve the best known approximation ratio based on local search from \$25+\veps\$ to \$9+\veps\$. For \$k\$-MedP, we obtain the best known approximation ratio. For \$k\$-MedO/\$k\$-MeaO, there exists only two bi-criteria approximation algorithms based on local search. One violates the outlier constraint (the constraint on the number of outliers), while the other violates the cardinality constraint (the constraint on the number of clusters). We consider the former algorithm and improve its approximation ratios from \$17+\veps\$ to \$3+\veps\$ for \$k\$-MedO, and from \$274+\veps\$ to \$9+\veps\$ for \$k\$-MeaO.  (Joint work with Yishui Wang, Rolf H. Mohring, Chenchen Wu, and Dongmei Zhang).

2020年12月1日

.