Document Open Access Logo

Tight Hardness Results for Maximum Weight Rectangles

Authors Arturs Backurs, Nishanth Dikkala, Christos Tzamos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.81.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Arturs Backurs
Nishanth Dikkala
Christos Tzamos

Cite As Get BibTex

Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.81

Abstract

Given n weighted points (positive or negative) in d dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains?

The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [Chan, FOCS, 2013], and runs in time O(n^d). It was conjectured [Barbay et al., CCCG, 2013] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems.

All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.

Subject Classification

Keywords
  • Maximum Rectangles
  • Hardness in P

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 98-117. IEEE, 2015. Google Scholar
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1681-1697. SIAM, 2015. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 41-50. ACM, 2015. Google Scholar
  4. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 434-443. IEEE, 2014. Google Scholar
  5. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Automata, Languages, and Programming, pages 39-51. Springer, 2014. Google Scholar
  6. Deepak Agarwal, Jeff M Phillips, and Suresh Venkatasubramanian. The hunting of the bump: on maximizing statistical discrepancy. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1137-1146. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  7. Jonathan Backer and J Mark Keil. The mono-and bichromatic empty rectangle and square problems in all dimensions. In LATIN 2010: Theoretical Informatics, pages 14-25. Springer, 2010. Google Scholar
  8. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. arXiv preprint arXiv:1602.05837, 2016. URL: http://arxiv.org/abs/1602.05837.
  9. Jérémy Barbay, Timothy M Chan, Gonzalo Navarro, and Pablo Pérez-Lantero. Maximum-weight planar boxes in o (n²) time (and better). Information Processing Letters, 114(8):437-445, 2014. Google Scholar
  10. Jon Bentley. Programming pearls: algorithm design techniques. Communications of the ACM, 27(9):865-873, 1984. Google Scholar
  11. Timothy M Chan. A (slightly) faster algorithm for klee’s measure problem. In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 94-100. ACM, 2008. Google Scholar
  12. Timothy M Chan. Klee’s measure problem made easy. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 410-419. IEEE, 2013. Google Scholar
  13. Chih-Huai Cheng, Kuan-Yu Chen, Wen-Chin Tien, and Kun-Mao Chao. Improved algorithms for the k maximum-sums problems. In Algorithms and Computation, pages 799-808. Springer, 2005. Google Scholar
  14. C Cortés, José Miguel Díaz-Báñez, Pablo Pérez-Lantero, Carlos Seara, Jorge Urrutia, and Inmaculada Ventura. Bichromatic separability with two boxes: a general approach. Journal of Algorithms, 64(2):79-88, 2009. Google Scholar
  15. David P Dobkin and Dimitrios Gunopulos. Computing the rectangle discrepancy. In Proceedings of the tenth annual symposium on Computational geometry, pages 385-386. ACM, 1994. Google Scholar
  16. David P Dobkin, Dimitrios Gunopulos, and Wolfgang Maass. Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning. journal of computer and system sciences, 52(3):453-470, 1996. Google Scholar
  17. Jonathan Eckstein, Peter L Hammer, Ying Liu, Mikhail Nediak, and Bruno Simeone. The maximum box problem and its application to data analysis. Computational Optimization and Applications, 23(3):285-298, 2002. Google Scholar
  18. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1):57-67, 2004. Google Scholar
  19. Paul Fischer, Klaus-U Höffgen, Hanno Lefmann, and Tomasz Luczak. Approximations with axis-aligned rectangles. In Fundamentals of Computation Theory, pages 244-255. Springer, 1993. Google Scholar
  20. Takeshi Fukuda, Yasukiko Morimoto, Shinichi Morishita, and Takeshi Tokuyama. Data mining using two-dimensional optimized association rules: Scheme, algorithms, and visualization. ACM SIGMOD Record, 25(2):13-23, 1996. Google Scholar
  21. Anka Gajentaan and Mark H Overmars. On a class of o (n 2) problems in computational geometry. Computational geometry, 5(3):165-185, 1995. Google Scholar
  22. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303. ACM, 2014. Google Scholar
  23. Ying Liu and Mikhail Nediak. Planar case of the maximum box and related problems. In CCCG, pages 14-18, 2003. Google Scholar
  24. Wolfgang Maass. Efficient agnostic pac-learning with simple hypothesis. In Proceedings of the seventh annual conference on Computational learning theory, pages 67-75. ACM, 1994. Google Scholar
  25. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  26. Mark H Overmars and Chee-Keng Yap. New upper bounds in klee’s measure problem. SIAM Journal on Computing, 20(6):1034-1045, 1991. Google Scholar
  27. Kalyan Perumalla and Narsingh Deo. Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters, 5(03):367-373, 1995. Google Scholar
  28. Ke Qiu and Selim G Akl. Parallel maximum sum algorithms on interconnection networks. In Proceedings of the Eleventh IAESTED Conference on Parallel and Distributed Computing and Systems, pages 31-38. Citeseer, 1999. Google Scholar
  29. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In Algorithms-ESA 2004, pages 580-591. Springer, 2004. Google Scholar
  30. Douglas R Smith. Applications of a strategy for designing divide-and-conquer algorithms. Science of Computer Programming, 8(3):213-229, 1987. Google Scholar
  31. Tadao Takaoka. Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electronic Notes in Theoretical Computer Science, 61:191-200, 2002. Google Scholar
  32. Hisao Tamaki and Takeshi Tokuyama. Algorithms for the maxium subarray problem based on matrix multiplication. In SODA, volume 1998, pages 446-452, 1998. Google Scholar
  33. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In LIPIcs-Leibniz International Proceedings in Informatics, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  34. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 664-673. ACM, 2014. Google Scholar
  35. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 887-898. ACM, 2012. Google Scholar
  36. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 645-654. IEEE, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact