PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Hardness Results for Maximum Weight Rectangles

Arturs Backurs, Nishanth Dikkala, Christos Tzamos

arXiv:1602.05837v2cs.DScs.CCcs.CG

TL;DR

The paper studies whether maximum-weight rectangles and related subarray problems admit substantially faster algorithms. It gives conditional lower bounds through reductions to APSP and Max-Weight k-Clique. The results indicate that polynomial-factor improvements would require faster algorithms for those graph problems.

  • Problem

    The paper addresses whether maximum-weight rectangle algorithms can be improved by polynomial factors despite a known quadratic-time planar algorithm and conjectures that strongly subquadratic time is impossible.

    Source: §1 · p. 1, §1.2 · p. 3

  • Method

    The paper reduces weighted clique and APSP instances to maximum-weight rectangle and subarray problems to derive conditional lower bounds.

    Source: §1 · p. 2, §1.2 · p. 3

  • Results

    An O(N^(2−ε)) planar MAX-WEIGHT RECTANGLE algorithm would imply an O(n^(⌈4/ε⌉−ε)) MAX-WEIGHT ⌈4/ε⌉-CLIQUE algorithm, while an O(n^(3−ε)) MAXIMUM SUBARRAY algorithm would imply an O(n^(3−ε/10)) APSP algorithm.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    The results make polynomial-factor improvements to the studied bounds conditional on breakthroughs for APSP or Max-Weight k-Clique.

    Source: §1 · p. 2, §1.2 · p. 3

    For d-dimensional MAXIMUM SUBARRAY, the O(n^(2d−1)) best known upper bound leaves a gap, and closing it requires better understanding of MAX-WEIGHT CLIQUE WITHOUT MATCHING.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

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 [T. M. Chan, FOCS'13], and runs in time $O(n^d)$. It was conjectured [Barbay et al., CCCG'13] 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.

1 Introduction

The paper argues that polynomial-factor improvements to maximum-weight rectangle and related subarray algorithms would require breakthroughs for fundamental graph problems. It develops conditional lower bounds for these problems and related variants, using assumptions about APSP and Max-Weight k-Clique.

1.1 Related work on the problems

  • Prior bounds include O(N²) for planar MAX-WEIGHT RECTANGLE, O(N^d) in d dimensions, and O(n^(2d−1)) for d-dimensional MAXIMUM SUBARRAY.For square-grid inputs, the structure permits an O(n³) algorithm, versus O(N²) for general planar rectangles.Source: §1 · p. 1, §1.1 · pp. 2–3

1.2 Our results and techniques

  • An O(N^(2−ε)) planar MAX-WEIGHT RECTANGLE algorithm would yield an O(n^(⌈4/ε⌉−ε)) MAX-WEIGHT ⌈4/ε⌉-CLIQUE algorithm, and the lower bound extends to d dimensions.For d-dimensional points, an O(N^(d−ε)) algorithm implies an O(n^(k−ε)) algorithm for MAX-WEIGHT k-CLIQUE, with k = ⌈d²/ε⌉; this matches the known upper bound up to subpolynomial factors.Source: §1.2 · p. 3
  • The rectangle reduction encodes clique nodes as base-n digits in box coordinates and uses O(n^(⌈k/d⌉+1)) points to represent weighted k-cliques.Source: §1.2 · p. 3
  • An O(n^(3−ε)) algorithm for n × n MAXIMUM SUBARRAY would give an O(n^(3−ε/10)) APSP algorithm; together with the known reverse reduction, the problems are equivalent for strongly subcubic algorithms.Source: §1.2 · pp. 3–4
  • For d-dimensional MAXIMUM SUBARRAY, the paper reduces MAX-WEIGHT CLIQUE WITHOUT MATCHING to the array problem and derives an O(n^(3d/2−ε))-to-O(n^(k−ε)) conditional implication.The text notes that the best known upper bound is O(n^(2d−1)) and that closing the gap remains open.Source: §1.2 · p. 4
  • MAXIMUM SQUARE SUBARRAY has a trivial O(n^(d+1)) enumeration algorithm, for which the paper gives a matching lower bound based on MAX-WEIGHT k-CLIQUE hardness.Source: §1.2 · p. 4
  • The paper also adapts a Klee’s measure reduction to establish a conditional lower bound for WEIGHTED DEPTH.Source: §1.2 · p. 4
  • The lower bounds also extend to weights restricted to +1 or −1, with the same runtime exponents for combinatorial algorithms; improving them would yield a faster combinatorial k-CLIQUE-DETECTION algorithm.The paper contrasts its assumptions with 3-SUM-based hardness work and notes that reducing 3-SUM to these problems seems difficult.Source: §1.2 · p. 4

2 Preliminaries

The paper studies maximum-weight boxes, subarrays, and hypercube subarrays, alongside weighted-depth and graph problems used in its hardness assumptions. Its reductions rely on APSP and maximum-weight clique hardness.

2.1 Problems studied in this work

  • MAX-WEIGHT RECTANGLE seeks an axis-aligned box maximizing the total weight of contained points, while MAXIMUM SUBARRAY maximizes the sum in a multidimensional array subarray.MAX-WEIGHT SQUARE restricts the subarray to a square or hypercube, and WEIGHTED DEPTH instead seeks a point covered by boxes with maximum total weight.Source: §2.1 · p. 5

2.2 Hardness assumptions

  • The hardness assumptions include APSP, NEGATIVE TRIANGLE, and MAX-WEIGHT k-CLIQUE; the paper also uses an equivalent k-partite version of the clique problem.For fixed k, the stated best-known MAX-WEIGHT k-CLIQUE algorithm runs in O(n^k−o(1)) time.Source: §2.2 · pp. 5–6
  • The notation [n] denotes {1, 2, ..., n}, and S^d denotes the set of d-tuples drawn from S.The passage introduces these conventions for the paper's later definitions and reductions.Source: §2.2 · p. 6

3 Hardness of the MAX-WEIGHT RECTANGLE problem

For any fixed dimension, the paper reduces maximum-weight clique to MAX-WEIGHT RECTANGLE, yielding a conditional lower bound matching the known runtime up to subpolynomial factors. The reduction routes through RESTRICTED RECTANGLE and preserves both box constraints and clique weights.

3 Hardness of the MAX-WEIGHT RECTANGLE problem

  • An O(N^(d−ε)) MAX-WEIGHT RECTANGLE algorithm would yield an O(n^(⌈d²/ε⌉−ε)) MAX-WEIGHT ⌈d²/ε⌉-CLIQUE algorithm.The construction uses O(n^(k+1)) points for a k-clique instance, and the result matches the known upper bound up to subpolynomial factors.Source: §3 · p. 6

3.1 RESTRICTED RECTANGLE ⇒MAX-WEIGHT RECTANGLE

  • The intermediate RESTRICTED RECTANGLE instance is converted by adding points that force an optimal box to satisfy the required constraints.A sufficiently large weight at the origin forces the box to contain it, and the added points preserve a total instance size of O(N).Source: §3 · p. 6, §3.1 · p. 7

3 Hardness of the MAX-WEIGHT RECTANGLE problem

  • The reduction first encodes each coordinate as k base-n digits, using those digits to represent vertices in the corresponding parts of a multipartite clique.The constructed rectangle instance has N = O(n^(k+1)) points; clique weights are encoded by point weights associated with within- and cross-coordinate edges.Source: §3 · p. 6, §3.2 · pp. 7–8

3.2 MAX-WEIGHT (d × k)-PARTITE CLIQUE ⇒RESTRICTED RECTANGLE

  • For every allowed box, the reduction makes its total weight equal the weight of the corresponding d×k-partite clique.The construction handles edges within a coordinate and between coordinates; when a+b is too large, it reverses the coordinate representation to keep the point count controlled.Source: §3.2 · pp. 7–8

4 Hardness for MAXIMUM SUBARRAY in 2 dimensions

The paper reduces POSITIVE TRIANGLE detection through MAXIMUM 4-COMBINATION to MAXIMUM SUBARRAY. Consequently, a strongly subcubic MAXIMUM SUBARRAY algorithm would imply a faster APSP algorithm.

4 Hardness for MAXIMUM SUBARRAY in 2 dimensions

  • An O(n^(3−ε)) algorithm for MAXIMUM SUBARRAY on n×n matrices implies an O(n^(3−ε/10)) APSP algorithm.The reduction proceeds through NEGATIVE TRIANGLE, for which an O(n^(3−ε)) algorithm implies the stated APSP runtime.Source: §4 · p. 8
  • The first reduction maps POSITIVE TRIANGLE to MAXIMUM 4-COMBINATION on a 2n×2n matrix.MAXIMUM 4-COMBINATION maximizes B[i,j] + B[i′,j′] − B[i,j′] − B[i′,j] over i≤i′ and j≤j′.Source: §4 · p. 9

4.1 POSITIVE TRIANGLE ⇒MAXIMUM 4-COMBINATION

  • The constructed 4-COMBINATION value equals the corresponding triangle weight plus M′ and M′′, where M′=10M and M′′=100M.The offsets force the maximizing indices to satisfy i,j≤n and i′=j′=k+n, allowing the expression to encode the triangle through A[i,j] + A[j,k] + A[k,i].Source: §4.1 · p. 9

4.2 MAXIMUM 4-COMBINATION ⇒MAXIMUM SUBARRAY

  • The second reduction defines C[i,j] as A′[i,j] + A′[i+1,j+1] − A′[i,j+1] − A′[i+1,j], and MAXIMUM SUBARRAY on C equals MAXIMUM 4-COMBINATION on A′.A′ is an (n+1)×(n+1) matrix, with A′[i,j] = A[i−1,j−1] when i,j ≥ 2 and zero otherwise.Source: §4.2 · p. 10

5 Hardness for MAXIMUM SUBARRAY for arbitrary number of dimensions

For constant d, the section reduces MAXIMUM SUBARRAY hardness to MAX-WEIGHT CLIQUE hardness through a sequence of intermediate problems. In particular, faster algorithms for the d-dimensional problem would yield faster algorithms for a corresponding clique problem.

5 Hardness for MAXIMUM SUBARRAY for arbitrary number of dimensions

  • An O(n^d) reduction sequence connects MAX-WEIGHT (d + ⌊d/2⌋)-CLIQUE to d-dimensional MAXIMUM SUBARRAY, so a faster subarray algorithm would imply a faster clique algorithm.The reductions take O(n^d) time when d = O(1).Source: §5 · pp. 11–12

5.1 MAX-WEIGHT (d + ⌊d/2⌋)-CLIQUE ⇒MAX-WEIGHT 2d-SUBGRAPH PROBLEM

  • The maximum weight of a (d + ⌊d/2⌋)-clique equals the maximum weight 2d-subgraph in the constructed graph.The construction adds paired vertex sets and uses sufficiently large negative edge weights to enforce the required choices.Source: §5.1 · pp. 12–13

5.2 MAX-WEIGHT 2d-SUBGRAPH PROBLEM ⇒CENTRAL MAXIMUM SUBARRAY SUM

  • The central-array construction makes CENTRAL MAXIMUM SUBARRAY SUM equal to the maximum 2d-subgraph weight multiplied by 2^(d−2).Entries encode d-clique weights; sufficiently negative entries discourage subarrays that violate the coordinate constraints.Source: §5.2 · p. 13

NATION

  • CENTRAL MAXIMUM SUBARRAY SUM and CENTRAL MAXIMUM SUBARRAY COMBINATION have equal outputs after a sign-based entry transformation.Subsequent transformations preserve the optimum while removing the centrality restriction, with an additive offset in the central-combination to combination step.Source: NATION · pp. 13–14

5.5 MAXIMUM SUBARRAY COMBINATION ⇒MAXIMUM SUBARRAY

  • The final reduction converts MAXIMUM SUBARRAY COMBINATION on a side-length 2n + 1 array to MAXIMUM SUBARRAY on side length 2n, preserving the output.It defines corresponding objectives over the same index and displacement choices.Source: §5.5 · p. 14

6 Hardness for MAXIMUM SQUARE SUBARRAY problem

For constant d ≥ 3, the section gives a conditional lower bound for MAXIMUM SQUARE SUBARRAY via reductions from MAX-WEIGHT CLIQUE. The proof proceeds through central and unrestricted combination problems before reaching the square-subarray problem.

6 Hardness for MAXIMUM SQUARE SUBARRAY problem

  • An O(n^(d+1−ε)) algorithm for d-dimensional MAXIMUM SQUARE SUBARRAY would give an O(n^(d+1−ε)) algorithm for MAX-WEIGHT (d + 1)-CLIQUE.The implication is stated for constant d ≥ 3.Source: §6 · p. 15

6.1 MAX-WEIGHT (d + 1)-CLIQUE ⇒CENTRAL MAX-SUM

  • A constructed array of side length 2dn + 1 lets CENTRAL MAX-SUM recover the maximum total edge weight of a (d + 1)-clique in constant time.The construction encodes d-clique weights in the array and uses a sufficiently large penalty for invalid tuples.Source: §6.1 · p. 16

6.2 CENTRAL MAX-SUM ⇒CENTRAL MAXIMUM COMBINATION

  • CENTRAL MAX-SUM reduces to CENTRAL MAXIMUM COMBINATION by a transformation whose correctness follows from the problem definitions.Both problems use arrays of side length 2n + 1.Source: §6.2 · p. 17

6.3 CENTRAL MAXIMUM COMBINATION ⇒MAXIMUM COMBINATION

  • CENTRAL MAXIMUM COMBINATION reduces to MAXIMUM COMBINATION by modifying the array to enforce the centrality constraints without changing the optimum.The construction adds a large value to selected entries and rules out choices that violate the constraints.Source: §6.3 · pp. 17–18

6.4 MAXIMUM COMBINATION ⇒MAXIMUM SQUARE SUBARRAY

  • MAXIMUM COMBINATION on a side-length n array reduces to MAXIMUM SQUARE SUBARRAY on side length n − 1 with equal outputs.The reduction aligns the square-subarray and combination objectives over corresponding index and displacement choices.Source: §6.4 · p. 18

7 Hardness for WEIGHTED DEPTH problem

The section proves a conditional lower bound for WEIGHTED DEPTH by reducing from maximum-weight clique in an edge-weighted graph.

7 Hardness for WEIGHTED DEPTH problem

  • An O(N^(d/2−ε)) algorithm for WEIGHTED DEPTH would imply an O(n^(d−2ε)) algorithm for maximum-weight d-clique.The proof adapts a reduction used for conditional lower bounds on combinatorial algorithms for Klee’s measure problem.Source: §7 · p. 18
  • The reduction creates O(n^2) weighted rectangles from graph edges, assigning each rectangle the weight of its corresponding edge.For each pair of distinct coordinates, the rectangle constrains those coordinates to the intervals associated with the edge’s endpoints.Source: §7 · pp. 18–19
  • The heaviest point in the constructed domain has twice the weight of the heaviest d-clique, and each d-clique’s weight is half that of its corresponding point.The construction shifts edge weights so they are positive before making this correspondence.Source: §7 · p. 19
Loading 1602.05837v2…