Tootfinder

Perfect Network Resilience in Polynomial Time
Matthias Bentert, Stefan Schmid
https://arxiv.org/abs/2602.03827 https://arxiv.org/pdf/2602.03827 https://arxiv.org/html/2602.03827
arXiv:2602.03827v1 Announce Type: new
Abstract: Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. The rerouting decisions at any node $v$ must rely solely on local information available at $v$: the link from which a packet arrived at $v$, the target of the packet, and the incident link failures at $v$. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source to its target as long as the two are connected in the underlying graph after the link failures. Already in their seminal paper at ACM PODC '12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that perfect resilience cannot always be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable.
This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an $O(n)$-time algorithm to decide whether a given instance is perfectly resilient and an $O(nm)$-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative.
toXiv_bot_toot

Replaced article(s) found for cs.GT. https://arxiv.org/list/cs.GT/new
[1/1]:
- Cumulative Games: Who is the current player?
Urban Larsson, Reshef Meir, Yair Zick
https://arxiv.org/abs/2005.06326
- Contest Design with Threshold Objectives
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
https://arxiv.org/abs/2109.03179
- Deep Learning Meets Mechanism Design: Key Results and Some Novel Applications
V. Udaya Sankar, Vishisht Srihari Rao, Y. Narahari
https://arxiv.org/abs/2401.05683 https://mastoxiv.page/@arXiv_csGT_bot/111741115483021453
- Charting the Shapes of Stories with Game Theory
Daskalakis, Gemp, Jiang, Leme, Papadimitriou, Piliouras
https://arxiv.org/abs/2412.05747 https://mastoxiv.page/@arXiv_csGT_bot/113627246220336424
- Computing Evolutionarily Stable Strategies in Multiplayer Games
Sam Ganzfried
https://arxiv.org/abs/2511.20859 https://mastoxiv.page/@arXiv_csGT_bot/115620508246637361
- Autodeleveraging: Impossibilities and Optimization
Tarun Chitra
https://arxiv.org/abs/2512.01112 https://mastoxiv.page/@arXiv_csGT_bot/115649040881525135
- Static Pricing Guarantees for Queueing Systems
Jacob Bergquist, Adam N. Elmachtoub
https://arxiv.org/abs/2305.09168 https://mastoxiv.page/@arXiv_csDS_bot/110382625621173269
- Game of arrivals at a two queue network with heterogeneous customer routes
Agniv Bandyopadhyay, Sandeep Juneja
https://arxiv.org/abs/2310.18149 https://mastoxiv.page/@arXiv_csPF_bot/111322112226936579
- Characterization of Priority-Neutral Matching Lattices
Clayton Thomas
https://arxiv.org/abs/2404.02142 https://mastoxiv.page/@arXiv_econTH_bot/112205968984928881
- Seven kinds of equivalent models for generalized coalition logics
Zixuan Chen, Fengkui Ju
https://arxiv.org/abs/2501.05466 https://mastoxiv.page/@arXiv_csLO_bot/113819715349259373
- Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Hadi Hosseini, Samarth Khanna, Ronak Singh
https://arxiv.org/abs/2506.04478 https://mastoxiv.page/@arXiv_csAI_bot/114635186215388479
toXiv_bot_toot

HALO: A Fine-Grained Resource Sharing Quantum Operating System
John Zhuoyang Ye, Jiyuan Wang, Yifan Qiao, Jens Palsberg
https://arxiv.org/abs/2602.07191 https://arxiv.org/pdf/2602.07191 https://arxiv.org/html/2602.07191
arXiv:2602.07191v1 Announce Type: new
Abstract: As quantum computing enters the cloud era, thousands of users must share access to a small number of quantum processors. Users need to wait minutes to days to start their jobs, which only takes a few seconds for execution. Current quantum cloud platforms employ a fair-share scheduler, as there is no way to multiplex a quantum computer among multiple programs at the same time, leaving many qubits idle and significantly under-utilizing the hardware. This imbalance between high user demand and scarce quantum resources has become a key barrier to scalable and cost-effective quantum computing.
We present HALO, the first quantum operating system design that supports fine-grained resource-sharing. HALO introduces two complementary mechanisms. First, a hardware-aware qubit-sharing algorithm that places shared helper qubits on regions of the quantum computer that minimize routing overhead and avoid cross-talk noise between different users' processes. Second, a shot-adaptive scheduler that allocates execution windows according to each job's sampling requirements, improving throughput and reducing latency. Together, these mechanisms transform the way quantum hardware is scheduled and achieve more fine-grained parallelism.
We evaluate HALO on the IBM Torino quantum computer on helper qubit intense benchmarks. Compared to state-of-the-art systems such as HyperQ, HALO improves overall hardware utilization by up to 2.44x, increasing throughput by 4.44x, and maintains fidelity loss within 33%, demonstrating the practicality of resource-sharing in quantum computing.
toXiv_bot_toot

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
Sharareh Alipour
https://arxiv.org/abs/2602.07720 https://arxiv.org/pdf/2602.07720 https://arxiv.org/html/2602.07720
arXiv:2602.07720v1 Announce Type: new
Abstract: Many multiagent tasks -- such as reviewer assignment, coalition formation, or fair resource allocation -- require selecting a group of agents such that collaboration remains effective even in the worst case. The \emph{weighted max-min $T$-join problem} formalizes this challenge by seeking a subset of vertices whose minimum-weight matching is maximized, thereby ensuring robust outcomes against unfavorable pairings.
We advance the study of this problem in several directions. First, we design an algorithm that computes an upper bound for the \emph{weighted max-min $2k$-matching problem}, where the chosen set must contain exactly $2k$ vertices. Building on this bound, we develop a general algorithm with a \emph{$2 \ln n$-approximation guarantee} that runs in $O(n^4)$ time. Second, using ear decompositions, we propose another upper bound for the weighted max-min $T$-join cost. We also show that the problem can be solved exactly when edge weights belong to $\{1,2\}$.
Finally, we evaluate our methods on real collaboration datasets. Experiments show that the lower bounds from our approximation algorithm and the upper bounds from the ear decomposition method are consistently close, yielding empirically small constant-factor approximations. Overall, our results highlight both the theoretical significance and practical value of weighted max-min $T$-joins as a framework for fair and robust group formation in multiagent systems.
toXiv_bot_toot

On Dynamic Programming Theory for Leader-Follower Stochastic Games
Jilles Steeve Dibangoye, Thibaut Le Marre, Ocan Sankur, Fran\c{c}ois Schwarzentruber
https://arxiv.org/abs/2512.05667 https://arxiv.org/pdf/2512.05667 https://arxiv.org/html/2512.05667
arXiv:2512.05667v1 Announce Type: new
Abstract: Leader-follower general-sum stochastic games (LF-GSSGs) model sequential decision-making under asymmetric commitment, where a leader commits to a policy and a follower best responds, yielding a strong Stackelberg equilibrium (SSE) with leader-favourable tie-breaking. This paper introduces a dynamic programming (DP) framework that applies Bellman recursion over credible sets-state abstractions formally representing all rational follower best responses under partial leader commitments-to compute SSEs. We first prove that any LF-GSSG admits a lossless reduction to a Markov decision process (MDP) over credible sets. We further establish that synthesising an optimal memoryless deterministic leader policy is NP-hard, motivating the development of {\epsilon}-optimal DP algorithms with provable guarantees on leader exploitability. Experiments on standard mixed-motive benchmarks-including security games, resource allocation, and adversarial planning-demonstrate empirical gains in leader value and runtime scalability over state-of-the-art methods.
toXiv_bot_toot

Fast $k$-means Seeding Under The Manifold Hypothesis
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
https://arxiv.org/abs/2602.01104 https://arxiv.org/pdf/2602.01104 https://arxiv.org/html/2602.01104
arXiv:2602.01104v1 Announce Type: new
Abstract: We study beyond worst case analysis for the $k$-means problem where the goal is to model typical instances of $k$-means arising in practice. Existing theoretical approaches provide guarantees under certain assumptions on the optimal solutions to $k$-means, making them difficult to validate in practice. We propose the manifold hypothesis, where data obtained in ambient dimension $D$ concentrates around a low dimensional manifold of intrinsic dimension $d$, as a reasonable assumption to model real world clustering instances. We identify key geometric properties of datasets which have theoretically predictable scaling laws depending on the quantization exponent $\varepsilon = 2/d$ using techniques from optimum quantization theory. We show how to exploit these regularities to design a fast seeding method called $\operatorname{Qkmeans}$ which provides $O(\rho^{-2} \log k)$ approximate solutions to the $k$-means problem in time $O(nD) \widetilde{O}(\varepsilon^{1 \rho}\rho^{-1}k^{1 \gamma})$; where the exponent $\gamma = \varepsilon \rho$ for an input parameter $\rho < 1$. This allows us to obtain new runtime - quality tradeoffs. We perform a large scale empirical study across various domains to validate our theoretical predictions and algorithm performance to bridge theory and practice for beyond worst case data clustering.
toXiv_bot_toot