{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiehekkjpfp2by6q2cm6o4nrvm7e6hczrbpntqizufchgaqnc7j6iy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhzke4vfing2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.25449v1",
  "publishedAt": "2026-03-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Geri Gokaj",
    "Marvin Künnemann",
    "Sabine Storandt",
    "Carina Truschel"
  ],
  "textContent": "**Authors:** Geri Gokaj, Marvin Künnemann, Sabine Storandt, Carina Truschel\n\nThe Pareto sum of two-dimensional point sets $P$ and $Q$ in $\\mathbb{R}^2$ is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets $P$ and $Q$ of size $n$ suffers from conditional lower bounds that rule out strongly subquadratic $O(n^{2-ε})$-time algorithms, even when the output size is $Θ(n)$. Naturally, we ask: How efficiently can we \\emph{approximate} Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is \\emph{fine-grained equivalent} to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable $\\tilde{O}(n^{1.5})$-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.",
  "title": "Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution"
}