{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaennjwrdbcf5osz2wt3pu6qvrzthfhr5taaacwttypqlups7uhrm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf4amhk7uc62"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.15314v1",
  "publishedAt": "2026-02-18T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Vincent Jugé",
    "Dominik Köppl",
    "Vincent Limouzy",
    "Andrea Marino",
    "Jannik Olblich",
    "Giulia Punzi",
    "Takeaki Uno"
  ],
  "textContent": "**Authors:** Vincent Jugé, Dominik Köppl, Vincent Limouzy, Andrea Marino, Jannik Olblich, Giulia Punzi, Takeaki Uno\n\nThe sparse matrix compression problem asks for a one-dimensional representation of a binary $n \\times \\ell$ matrix, formed by an integer array of row indices and a shift function for each row, such that accessing a matrix entry is possible in constant time by consulting this representation. It has been shown that the decision problem for finding an integer array of length $\\ell+ρ$ or restricting the shift function up to values of $ρ$ is NP-complete (cf. the textbook of Garey and Johnson). As a practical heuristic, a greedy algorithm has been proposed to shift the $i$-th row until it forms a solution with its predecessor rows. Despite that this greedy algorithm is cherished for its good approximation in practice, we show that it actually exhibits an approximation ratio of $Θ(\\sqrt{\\ell+ρ})$. We give further hardness results for parameterizations such as the number of distinct rows or the maximum number of non-zero entries per row. Finally, we devise a DP-algorithm that solves the problem for double-logarithmic matrix widths or logarithmic widths for further restrictions. We study all these findings also under a new perspective by introducing a variant of the problem, where we wish to minimize the length of the resulting integer array by trimming the non-zero borders, which has not been studied in the literature before but has practical motivations.",
  "title": "Revisiting the Sparse Matrix Compression Problem"
}