Approximation algorithms for array partitioning problems

S. Muthukrishnan; Torsten Suel

doi:10.1016/j.jalgor.2003.11.006

Approximation algorithms for array partitioning problems

S. Muthukrishnan, Torsten Suel

Research output: Contribution to journal › Article › peer-review

Abstract

We study the problem of optimally partitioning a two-dimensional array of elements by cutting each coordinate axis into p (respectively, q) intervals, resulting in p × q rectangular regions. This problem arises in several applications in databases, parallel computation, and image processing. Our main contribution are new approximation algorithms for these NP-complete problems that improve significantly over previously known bounds. The algorithms are fast and simple, work for a variety of measures of partitioning quality, generalize to dimensions d > 2, and achieve almost optimal approximation ratios. We also extend previous NP-completeness results for this class of problems.

Original language	English (US)
Pages (from-to)	85-104
Number of pages	20
Journal	Journal of Algorithms
Volume	54
Issue number	1
DOIs	https://doi.org/10.1016/j.jalgor.2003.11.006
State	Published - Jan 2005

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/j.jalgor.2003.11.006

Cite this

@article{1520e5134a3349c280a769114333fd60,

title = "Approximation algorithms for array partitioning problems",

abstract = "We study the problem of optimally partitioning a two-dimensional array of elements by cutting each coordinate axis into p (respectively, q) intervals, resulting in p × q rectangular regions. This problem arises in several applications in databases, parallel computation, and image processing. Our main contribution are new approximation algorithms for these NP-complete problems that improve significantly over previously known bounds. The algorithms are fast and simple, work for a variety of measures of partitioning quality, generalize to dimensions d > 2, and achieve almost optimal approximation ratios. We also extend previous NP-completeness results for this class of problems.",

author = "S. Muthukrishnan and Torsten Suel",

year = "2005",

month = jan,

doi = "10.1016/j.jalgor.2003.11.006",

language = "English (US)",

volume = "54",

pages = "85--104",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Approximation algorithms for array partitioning problems

AU - Muthukrishnan, S.

AU - Suel, Torsten

PY - 2005/1

Y1 - 2005/1

N2 - We study the problem of optimally partitioning a two-dimensional array of elements by cutting each coordinate axis into p (respectively, q) intervals, resulting in p × q rectangular regions. This problem arises in several applications in databases, parallel computation, and image processing. Our main contribution are new approximation algorithms for these NP-complete problems that improve significantly over previously known bounds. The algorithms are fast and simple, work for a variety of measures of partitioning quality, generalize to dimensions d > 2, and achieve almost optimal approximation ratios. We also extend previous NP-completeness results for this class of problems.

AB - We study the problem of optimally partitioning a two-dimensional array of elements by cutting each coordinate axis into p (respectively, q) intervals, resulting in p × q rectangular regions. This problem arises in several applications in databases, parallel computation, and image processing. Our main contribution are new approximation algorithms for these NP-complete problems that improve significantly over previously known bounds. The algorithms are fast and simple, work for a variety of measures of partitioning quality, generalize to dimensions d > 2, and achieve almost optimal approximation ratios. We also extend previous NP-completeness results for this class of problems.

UR - http://www.scopus.com/inward/record.url?scp=10644253543&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10644253543&partnerID=8YFLogxK

U2 - 10.1016/j.jalgor.2003.11.006

DO - 10.1016/j.jalgor.2003.11.006

M3 - Article

AN - SCOPUS:10644253543

SN - 0196-6774

VL - 54

SP - 85

EP - 104

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Approximation algorithms for array partitioning problems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this