{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:34Z","timestamp":1750306714506,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0729171","CCF-0845701"],"award-info":[{"award-number":["CCF-0729171","CCF-0845701"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            We provide improved approximation algorithms for the\n            <jats:italic>min-max generalization problems<\/jats:italic>\n            considered by Du, Eppstein, Goodrich, and Lueker [Du et al. 2009]. Generalization is widely used in privacy-preserving data mining and can also be viewed as a natural way of compressing a dataset. In min-max generalization problems, the input consists of data items with weights and a lower bound\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>lb<\/jats:sub>\n            , and the goal is to partition individual items into groups of weight at least\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>lb<\/jats:sub>\n            while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du et al. consider several problems in this vein: (1) partitioning a graph into connected subgraphs, (2) partitioning unstructured data into arbitrary classes, and (3) partitioning a two-dimensional array into contiguous rectangles (subarrays) that satisfy these weight requirements.\n          <\/jats:p>\n          <jats:p>We significantly improve approximation ratios for all the problems considered by Du et al. and provide additional motivation for these problems. Moreover, for the first problem, whereas Du et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work.<\/jats:p>","DOI":"10.1145\/2636920","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Min-Max Generalization Problems"],"prefix":"10.1145","volume":"11","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90004-X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_2_1_3_1","unstructured":"Piotr Berman Bhaskar DasGupta and S. Muthukrishnan. 2002. Slice and dice: A simple improved approximate tiling recipe. In SODA David Eppstein (Ed.). ACM\/SIAM 455--464.   Piotr Berman Bhaskar DasGupta and S. Muthukrishnan. 2002. Slice and dice: A simple improved approximate tiling recipe. In SODA David Eppstein (Ed.). ACM\/SIAM 455--464."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00015-4"},{"key":"e_1_2_1_5_1","unstructured":"Piotr Berman Bhaskar DasGupta S. Muthukrishnan and Suneeta Ramaswami. 2001. Improved approximation algorithms for rectangle tiling and packing. In SODA. 427--436.   Piotr Berman Bhaskar DasGupta S. Muthukrishnan and Suneeta Ramaswami. 2001. Improved approximation algorithms for rectangle tiling and packing. In SODA. 427--436."},{"volume-title":"APPROX-RANDOM(Lecture Notes in Computer Science), Maria J","author":"Berman Piotr","key":"e_1_2_1_6_1","unstructured":"Piotr Berman and Sofya Raskhodnikova . 2010. Approximation algorithms for min-max generalization problems . In APPROX-RANDOM(Lecture Notes in Computer Science), Maria J . Serna, Ronen Shaltiel, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.), Vol. 6302 . Springer , 53--66. Piotr Berman and Sofya Raskhodnikova. 2010. Approximation algorithms for min-max generalization problems. In APPROX-RANDOM(Lecture Notes in Computer Science), Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.), Vol. 6302. Springer, 53--66."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90012-6"},{"key":"e_1_2_1_8_1","volume-title":"S. Foresti, and P. Samarati.","author":"Ciriani V.","year":"2008","unstructured":"V. Ciriani , S. De Capitani di Vimercati , S. Foresti, and P. Samarati. 2008 . k-anonymous data mining: A survey. In Privacy-Preserving Data Mining: Models and Algorithms, Charu C. Aggarwal and Philip S. Yu (Eds.). Springer , Chapter 5. V. Ciriani, S. De Capitani di Vimercati, S. Foresti, and P. Samarati. 2008. k-anonymous data mining: A survey. In Privacy-Preserving Data Mining: Models and Algorithms, Charu C. Aggarwal and Philip S. Yu (Eds.). Springer, Chapter 5."},{"volume-title":"Better approximation algorithms for bin covering","author":"Csirik J\u00e1nos","key":"e_1_2_1_9_1","unstructured":"J\u00e1nos Csirik , David S. Johnson , and Claire Kenyon . 2001. Better approximation algorithms for bin covering . In SODA, S. Rao Kosaraju (Ed.). ACM\/SIAM , 557--566. J\u00e1nos Csirik, David S. Johnson, and Claire Kenyon. 2001. Better approximation algorithms for bin covering. In SODA, S. Rao Kosaraju (Ed.). ACM\/SIAM, 557--566."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_22"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/288692.288723"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00363-3"},{"volume-title":"On approximating rectangle tiling and packing","author":"Khanna Sanjeev","key":"e_1_2_1_14_1","unstructured":"Sanjeev Khanna , S. Muthukrishnan , and Mike Paterson . 1998. On approximating rectangle tiling and packing . In SODA, Howard J. Karloff (Ed.). ACM\/SIAM , 384--393. Sanjeev Khanna, S. Muthukrishnan, and Mike Paterson. 1998. On approximating rectangle tiling and packing. In SODA, Howard J. Karloff (Ed.). ACM\/SIAM, 384--393."},{"volume-title":"Algorithm Design","author":"Kleinberg Jon M.","key":"e_1_2_1_15_1","unstructured":"Jon M. Kleinberg and \u00c9va Tardos . 2006. Algorithm Design . Addison-Wesley . I--XXIII, 1--838. Jon M. Kleinberg and \u00c9va Tardos. 2006. Algorithm Design. Addison-Wesley. I--XXIII, 1--838."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan Viswanath Poosala and Torsten Suel. 1999. On rectangular partitionings in two dimensions: Algorithms complexity and applications. In ICDT. 236--256.   S. Muthukrishnan Viswanath Poosala and Torsten Suel. 1999. On rectangular partitionings in two dimensions: Algorithms complexity and applications. In ICDT. 236--256.","DOI":"10.1007\/3-540-49257-7_16"},{"volume-title":"FCT(Lecture Notes in Computer Science), Gabriel Ciobanu and Gheorghe P\u0103un (Eds.)","author":"Sharp Jonathan P.","key":"e_1_2_1_19_1","unstructured":"Jonathan P. Sharp . 1999. Tiling multi-dimensional arrays . In FCT(Lecture Notes in Computer Science), Gabriel Ciobanu and Gheorghe P\u0103un (Eds.) , Vol. 1684 . Springer , 500--511. Jonathan P. Sharp. 1999. Tiling multi-dimensional arrays. In FCT(Lecture Notes in Computer Science), Gabriel Ciobanu and Gheorghe P\u0103un (Eds.), Vol. 1684. Springer, 500--511."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1109"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0081471-8"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636920","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:22Z","timestamp":1750231162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636920"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2636920"],"URL":"https:\/\/doi.org\/10.1145\/2636920","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}