2024-04-18-dalirrooyfard24a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Graph Partitioning with a Move Budget	In many real world networks, there already exists a (not necessarily optimal) $k$-partitioning of the network. Oftentimes, for such networks, one aims to find a $k$-partitioning with a smaller cut value by moving only a few nodes across partitions. The number of nodes that can be moved across partitions is often a constraint forced by budgetary limitations. Motivated by such real-world applications, we introduce and study the $r$-move $k$-partitioning problem, a natural variant of the Multiway cut problem. Given a graph, a set of $k$ terminals and an initial partitioning of the graph, the $r$-move $k$-partitioning problem aims to find a $k$-partitioning with the minimum-weighted cut among all the $k$-partitionings that can be obtained by moving at most $r$ non-terminal nodes to partitions different from their initial ones. Our main result is a polynomial time $3(r+1)$ approximation algorithm for this problem. We further show that this problem is $W[1]$-hard, and give an FPTAS for when $r$ is a small constant.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	dalirrooyfard24a	0	Graph Partitioning with a Move Budget	568	576	568-576	568	false	Dalirrooyfard, Mina and Fata, Elaheh and Behbahani, Majid and Nevmyvaka, Yuriy	given family Mina Dalirrooyfard given family Elaheh Fata given family Majid Behbahani given family Yuriy Nevmyvaka	2024-04-18		Proceedings of The 27th International Conference on Artificial Intelligence and Statistics	238	inproceedings	date-parts 2024 4 18	https://proceedings.mlr.press/v238/dalirrooyfard24a/dalirrooyfard24a.pdf