Scholarlink

In this work, we study how to maintain a forest of arborescences of maximum arc cardinality under arc insertions while minimizing recourse—the total number of arcs changed in the maintained solution. This problem is the “arborescence version” of max cardinality matching. On the impossibility side, we observe that even in this insertion-only model, it is possible for m adversarial arc arrivals to necessarily incur \(\varOmega (m \cdot n)\) recourse, matching a trivial upper bound of \(O(m \cdot n)\) . On the possibility side, we give an algorithm with expected recourse \(O(m \cdot \log ^2 n)\) if all m arcs arrive uniformly at random.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Low Recourse Arborescence Forests Under Uniformly Random Arcs

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • J. Niklas Dahlmeier,
  • D. Ellis Hershkowitz

摘要

In this work, we study how to maintain a forest of arborescences of maximum arc cardinality under arc insertions while minimizing recourse—the total number of arcs changed in the maintained solution. This problem is the “arborescence version” of max cardinality matching. On the impossibility side, we observe that even in this insertion-only model, it is possible for m adversarial arc arrivals to necessarily incur \(\varOmega (m \cdot n)\) recourse, matching a trivial upper bound of \(O(m \cdot n)\) . On the possibility side, we give an algorithm with expected recourse \(O(m \cdot \log ^2 n)\) if all m arcs arrive uniformly at random.