CaltechAUTHORS
  A Caltech Library Service

Convex optimization for the planted k-disjoint-clique problem

Ames, Brendan P. W. and Vavasis, Stephen A. (2014) Convex optimization for the planted k-disjoint-clique problem. Mathematical Programming, 143 (1-2). pp. 299-337. ISSN 0025-5610. https://resolver.caltech.edu/CaltechAUTHORS:20140213-094722877

[img]
Preview
PDF - Submitted Version
See Usage Policy.

462Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140213-094722877

Abstract

We consider the k -disjoint-clique problem. The input is an undirected graph G in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph k disjoint cliques that cover the maximum number of nodes of G. This problem may be understood as a general way to pose the classical ‘clustering’ problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows ‘noise’ nodes to be present in the input data that are not part of any of the cliques. The k -disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of k disjoint large cliques (called ‘planted cliques’) that are then obscured by noise edges inserted either at random or by an adversary, as well as additional nodes not belonging to any of the k planted cliques.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s10107-013-0733-1DOIArticle
http://link.springer.com/article/10.1007%2Fs10107-013-0733-1PublisherArticle
http://arxiv.org/abs/1008.2814arXivDiscussion Paper
http://rdcu.be/twj9PublisherFree ReadCube access
Additional Information:© 2013 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. Received: 20 August 2010; Accepted: 9 October 2012; Published online: 7 December 2013. Supported in part by a Discovery Grant and Postgraduate Scholarship (Doctoral) from NSERC (Natural Science and Engineering Research Council of Canada), MITACS (Mathematics of Information Technology and Complex Systems), and the US Air Force Office of Scientific Research.
Funders:
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Mathematics of Information Technology and Complex Systems (MITACS)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Issue or Number:1-2
Classification Code:Mathematics Subject Classification: 90C22; 90C25; 68Q25; 62H302
Record Number:CaltechAUTHORS:20140213-094722877
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20140213-094722877
Official Citation:Ames, B. W., & Vavasis, S. (2014). Convex optimization for the planted k-disjoint-clique problem. Mathematical Programming, 143(1-2), 299-337. doi: 10.1007/s10107-013-0733-1
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:43808
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:13 Feb 2014 18:12
Last Modified:03 Oct 2019 06:11

Repository Staff Only: item control page