Solving Generalized Maximum Dispersion with Linear Programming
2007 (English)In: Proceedings of 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007) / [ed] M.-Y. Kao and X.-Y. Li, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2007, 1-10 p.Conference paper (Refereed)
The Generalized Maximum Dispersion problem asks for a partition of a given graph into p vertex-disjoint sets, each of them having at most k vertices. The goal is to maximize the total edge-weight of the induced subgraphs. We present the first LP-based approximation algorithm.
Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2007. 1-10 p.
, Lecture Notes in Computer Science, Volume 4508
Approximation Algorithms, Randomized Algorithms, Generalized Maximum Dispersion
IdentifiersURN: urn:nbn:se:umu:diva-84442OAI: oai:DiVA.org:umu-84442DiVA: diva2:684075
3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007)