{
  "abstract": "We study the problem of scheduling a single server among $K \\in \\mathbb{N}$ queues in a random environment of $M \\in \\mathbb{N}$ time-varying channels. Our framework is essentially that of Shakkottai and Stolyar (2002). We exhibit two distinct mathematical identifications of this problem, which yield complementary insight. The first identification is with a generalised network flow, an object studied in combinatorial optimisation. It yields a new characterisation of stability in terms of the existence of a generalised flow of maximum value and, via Végh (2017), strongly polynomial algorithms both to test the stability of a given arrival-rate vector and to compute a stabilising policy that is agnostic to queue lengths. In the ON/OFF case, first studied in Tassiulas and Ephremides (1993), this identification yields, through the max-flow/min-cut theorem, an independent proof of the explicit characterisation of the maximum stability region obtained there. The second identification is with a cephoid, a structure studied in convex geometry, mainly by Rosenmüller and Pallaschke, whose machinery it puts at our disposal. Under a non-degeneracy assumption on the channel gains, their results apply directly and yield an iterative procedure describing the geometry of the stability region precisely, providing a characterisation of the region by a minimal family of load inequalities as a very particular consequence. For $K=2$, these load inequalities become explicit in the parameters of the model, and we build on them to associate with any stabilisable arrival-rate vector a stabilising, queue-length-agnostic policy given in closed form.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": null,
  "author_total": 3,
  "authors": [
    {
      "name": "Nahuel Soprano-Loto"
    },
    {
      "name": "Urtzi Ayesta"
    },
    {
      "name": "Ina Maria Maaike Verloop"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/56gpyjgzw7e03.bib",
  "cited_by": 0,
  "doi": null,
  "fulltext_url": null,
  "id": "56gpyjgzw7e03",
  "issns": [],
  "landing_url": "https://hal.science/hal-05733315v1",
  "language": "en",
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "hal",
      "0.info"
    ],
    [
      "hal",
      "0.math"
    ],
    [
      "hal",
      "1.info.info-pf"
    ],
    [
      "hal",
      "1.info.info-ro"
    ],
    [
      "hal",
      "1.math.math-co"
    ],
    [
      "hal",
      "1.math.math-mg"
    ],
    [
      "hal",
      "1.math.math-oc"
    ],
    [
      "hal",
      "1.math.math-pr"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://hal.science/hal-05733315/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-08-31",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/56gpyjgzw7e03.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:24Z",
      "native_id": "hal-05733315",
      "source": "hal",
      "url": "https://hal.science/hal-05733315v1"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "hal:1.math.math-co",
      "subfield": "combinatorics"
    },
    {
      "field": "mathematics",
      "origin": "hal:1.math.math-mg",
      "subfield": "geometry-topology"
    },
    {
      "field": "mathematics",
      "origin": "hal:1.math.math-oc",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "hal:1.math.math-pr",
      "subfield": "probability"
    }
  ],
  "title": "On the stability of scheduling under a randomly varying channel: insights from generalised network flows and cephoids",
  "title_text": "On the stability of scheduling under a randomly varying channel: insights from generalised network flows and cephoids",
  "type": "preprint",
  "updated_at": "2026-10-30T12:17:24Z",
  "url": "https://research.draconitic.com/paper/56gpyjgzw7e03",
  "venue": "HAL",
  "versions": []
}