Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering

Nimita Shinde; Vishnu Narayanan; James Saunderson

Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering

Nimita Shinde
, Vishnu Narayanan
, James Saunderson

Electrical and Computer Systems Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

4 Citations (Scopus)

Abstract

MAX-K-CUT and correlation clustering are fundamental graph partitioning problems. For a graph G = (V, E) with n vertices, the methods with the best approximation guarantees for MAX-K-CUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O(n²) constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use O(n + |E|) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on |E| in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 34 (NeurIPS 2021)
Editors	Marc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
Place of Publication	San Diego CA USA
Publisher	Neural Information Processing Systems (NIPS)
Pages	8269-8281
Number of pages	13
ISBN (Electronic)	9781713845393
Publication status	Published - 2021
Event	Advances in Neural Information Processing Systems 2021 - Online, United States of America Duration: 7 Dec 2021 → 10 Dec 2021 Conference number: 35th https://papers.nips.cc/paper/2021 (Proceedings) https://nips.cc/Conferences/2021 (Website)

Publication series

Name	Advances in Neural Information Processing Systems
Volume	10
ISSN (Print)	1049-5258

Conference

Conference	Advances in Neural Information Processing Systems 2021
Abbreviated title	NeurIPS 2021
Country/Territory	United States of America
City	Online
Period	7/12/21 → 10/12/21
Internet address	https://papers.nips.cc/paper/2021 (Proceedings) https://nips.cc/Conferences/2021 (Website)

Access to Document

369971721-oaFinal published version, 372 KB

https://papers.nips.cc/paper/2021/file/45c166d697d65080d54501403b433256-Paper.pdf

Cite this

Shinde, N., Narayanan, V., & Saunderson, J. (2021). Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (pp. 8269-8281). (Advances in Neural Information Processing Systems; Vol. 10). Neural Information Processing Systems (NIPS). https://papers.nips.cc/paper/2021/file/45c166d697d65080d54501403b433256-Paper.pdf

Shinde, Nimita ; Narayanan, Vishnu ; Saunderson, James. / Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering. Advances in Neural Information Processing Systems 34 (NeurIPS 2021). editor / Marc'Aurelio Ranzato ; Alina Beygelzimer ; Yann Dauphin ; Percy S. Liang ; Jenn Wortman Vaughan. San Diego CA USA : Neural Information Processing Systems (NIPS), 2021. pp. 8269-8281 (Advances in Neural Information Processing Systems).

@inproceedings{5d8a5337d13c4f0fae9f7707bcd988bd,

title = "Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering",

abstract = "MAX-K-CUT and correlation clustering are fundamental graph partitioning problems. For a graph G = (V, E) with n vertices, the methods with the best approximation guarantees for MAX-K-CUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O(n2) constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use O(n + |E|) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on |E| in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.",

author = "Nimita Shinde and Vishnu Narayanan and James Saunderson",

note = "Funding Information: Funding in direct support of this work: scholarship for Nimita Shinde was provided by IITB-Monash Research Academy. Additionally, Dr. James Saunderson was supported in part by an Australian Research Council Discovery Early Career Researcher Award (project number DE210101056) funded by the Australian Government. Publisher Copyright: {\textcopyright} 2021 Neural information processing systems foundation. All rights reserved.; Advances in Neural Information Processing Systems 2021, NeurIPS 2021 ; Conference date: 07-12-2021 Through 10-12-2021",

year = "2021",

language = "English",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural Information Processing Systems (NIPS)",

pages = "8269--8281",

editor = "Marc'Aurelio Ranzato and Alina Beygelzimer and Yann Dauphin and Liang, \{Percy S.\} and \{Wortman Vaughan\}, Jenn",

booktitle = "Advances in Neural Information Processing Systems 34 (NeurIPS 2021)",

address = "United States of America",

url = "https://papers.nips.cc/paper/2021, https://nips.cc/Conferences/2021",

}

Shinde, N, Narayanan, V & Saunderson, J 2021, Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering. in MA Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), Advances in Neural Information Processing Systems 34 (NeurIPS 2021). Advances in Neural Information Processing Systems, vol. 10, Neural Information Processing Systems (NIPS), San Diego CA USA, pp. 8269-8281, Advances in Neural Information Processing Systems 2021, Online, United States of America, 7/12/21. <https://papers.nips.cc/paper/2021/file/45c166d697d65080d54501403b433256-Paper.pdf>

Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering. / Shinde, Nimita; Narayanan, Vishnu; Saunderson, James.
Advances in Neural Information Processing Systems 34 (NeurIPS 2021). ed. / Marc'Aurelio Ranzato; Alina Beygelzimer; Yann Dauphin; Percy S. Liang; Jenn Wortman Vaughan. San Diego CA USA: Neural Information Processing Systems (NIPS), 2021. p. 8269-8281 (Advances in Neural Information Processing Systems; Vol. 10).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering

AU - Shinde, Nimita

AU - Narayanan, Vishnu

AU - Saunderson, James

N1 - Conference code: 35th

PY - 2021

Y1 - 2021

N2 - MAX-K-CUT and correlation clustering are fundamental graph partitioning problems. For a graph G = (V, E) with n vertices, the methods with the best approximation guarantees for MAX-K-CUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O(n2) constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use O(n + |E|) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on |E| in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.

AB - MAX-K-CUT and correlation clustering are fundamental graph partitioning problems. For a graph G = (V, E) with n vertices, the methods with the best approximation guarantees for MAX-K-CUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O(n2) constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use O(n + |E|) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on |E| in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.

UR - https://www.scopus.com/pages/publications/85131812310

M3 - Conference Paper

AN - SCOPUS:85131812310

T3 - Advances in Neural Information Processing Systems

SP - 8269

EP - 8281

BT - Advances in Neural Information Processing Systems 34 (NeurIPS 2021)

A2 - Ranzato, Marc'Aurelio

A2 - Beygelzimer, Alina

A2 - Dauphin, Yann

A2 - Liang, Percy S.

A2 - Wortman Vaughan, Jenn

PB - Neural Information Processing Systems (NIPS)

CY - San Diego CA USA

T2 - Advances in Neural Information Processing Systems 2021

Y2 - 7 December 2021 through 10 December 2021

ER -

Shinde N, Narayanan V, Saunderson J. Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering. In Ranzato MA, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, editors, Advances in Neural Information Processing Systems 34 (NeurIPS 2021). San Diego CA USA: Neural Information Processing Systems (NIPS). 2021. p. 8269-8281. (Advances in Neural Information Processing Systems).

Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering

Abstract

Publication series

Conference

Access to Document

Other files and links

Realising the potential of hyperbolic programming

Cite this

Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Realising the potential of hyperbolic programming

Cite this