TY - GEN
T1 - Approximate kernel clustering
AU - Khot, Subhash
AU - Naor, Assaf
N1 - Funding Information:
Density functional theory (DFT) calculations have been performed to calculate the optimized geometries of stepwise fluorinated methylenecyclopropanes and 1-methylcyclopropenes. Increasing the number of fluorine atoms caused a destabilization of methylenecycopropane. Perfluorinated 1-methylcyclopropene was found to be present in substantial concentration. This is supported by calculations of the Gibbs free energy, isodesmic reactions and orbital energies (HOMO-LUMO). These results are compared with the fluorinated cyclopropanes keto-enol system. Enthalpies, entropies and dipole moments are reported.
PY - 2008
Y1 - 2008
N2 - In the kernel clustering problem we are given a large n × n positive semi-definite matrix A = (aij) with Σi,j=1 n aij = 0 and a small k × k positive semi-definite matrix B = (bij). The goal is to find a partition S1,.. .,Sk of{1,...n} which maximizes the quantity Σ i,j=1k (Σ(i,j)∈Si×Sj a ij) bij. We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the Unique Games Conjecture (UGC). In particular, when B is the 3 × 3 identity matrix the UGC hardness threshold of this problem is exactly 16π/27. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when B is the k × k identity matrix is 8π/9 (1-1/k) for every k ≥ 3.
AB - In the kernel clustering problem we are given a large n × n positive semi-definite matrix A = (aij) with Σi,j=1 n aij = 0 and a small k × k positive semi-definite matrix B = (bij). The goal is to find a partition S1,.. .,Sk of{1,...n} which maximizes the quantity Σ i,j=1k (Σ(i,j)∈Si×Sj a ij) bij. We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the Unique Games Conjecture (UGC). In particular, when B is the 3 × 3 identity matrix the UGC hardness threshold of this problem is exactly 16π/27. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when B is the k × k identity matrix is 8π/9 (1-1/k) for every k ≥ 3.
UR - http://www.scopus.com/inward/record.url?scp=57949086638&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57949086638&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2008.33
DO - 10.1109/FOCS.2008.33
M3 - Conference contribution
AN - SCOPUS:57949086638
SN - 9780769534367
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 561
EP - 570
BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Y2 - 25 October 2008 through 28 October 2008
ER -