{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicszvqq3e4njuyszhs7orr2katdjzi6hnv2xh6i3k5typv4hhsf2m",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mm5d3bvwkz22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.15745v1",
  "publishedAt": "2026-05-18T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ioannis Caragiannis",
    "Kostas Kollias",
    "Mohammad Roghani",
    "Aaron Schild",
    "Ali Kemal Sinop"
  ],
  "textContent": "**Authors:** Ioannis Caragiannis, Kostas Kollias, Mohammad Roghani, Aaron Schild, Ali Kemal Sinop\n\nAutonomous ride-hailing platforms must strategically position idle robotaxis to minimize the wait times of prospective riders. We formalize this as the \\emph{robotaxi placement problem} ($k$-RP). Given a finite metric space and a demand distribution over its points, the goal is to position $k$ robotaxis to minimize the expected total distance in a perfect matching between the robotaxis and $k$ random riders. We present several theoretical results for this stochastic optimization problem. First, we observe that sampling robotaxi locations independently according to the demand distribution yields a randomized $2$-approximation algorithm. Second, we present an explicit inapproximability bound via a novel gap-preserving reduction from the maximum coverage problem. Furthermore, while it is not even clear whether the exact expected cost of a placement can be computed efficiently on general metrics, we design an exact polynomial-time dynamic programming algorithm for $k$-RP in tree metrics by decoupling the stochastic matching dependencies. Finally, empirical evaluations on real-world ride-hailing data reveal that a variance-reduced random placement strategy is highly effective in practice, yielding expected wait times that are very close to those obtained by computationally heavy exact algorithms for the uniform capacitated $k$-median problem.",
  "title": "The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand"
}