Papers for

network planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Faster ways to find independent triples in overlapping disk groups

Computing Independent Sets of Size Three in Disk Graphs

Abstract: We study the problem of computing an independent set of size three in disk graphs, where vertices correspond to disks in the plane and two vertices are adjacent if their disks intersect. While computing a maximum independent set in disk graphs is NP-hard, the fixed-size case admits more efficient solutions. Given a set of $n$ disks, we present an algorithm to compute an independent set of size three in the disk graph and our algorithm runs in randomized expected $O^*(n^{5/3})$ time, where $O^*$ hides a factor of $n^ε$ for an arbitrarily small $ε> 0$. Our approach introduces a framework based on semi-algebraic range searching and tree-structured biclique partitions, which allows us to group pairs of disjoint disks into canonical subsets and avoid redundant computations. When the centers of the disks are in convex position, we solve the problem in $O(n \log^2 n)$ deterministic time. We also consider the case in which the disks themselves are in convex position, i.e., each disk contributes to the boundary of the convex hull of all disks, and obtain an $O(n \log^2 n)$ time algorithm for this setting as well. Our techniques for these cases are based on geometric properties of disk arrangements. In particular, they rely on new structural lemmas that reduce the problem to efficiently testing certain ordered configurations of disks. Our results improve upon the straightforward quadratic time approach and demonstrate how geometric structures and range searching techniques can be leveraged to solve fixed-size independent set problems in disk graphs more efficiently. To the best of our knowledge, this is the first systematic study of independent sets of size three in disk graphs. Our results show that even this smallest nontrivial case exhibits rich structural properties, especially under convexity assumptions.

Sat 14 NovComputational GeometryData Structures and Algorithms
The gist
Finding three disks that don’t overlap in a group of disks placed on a flat surface can be slow if done by checking every combination. The authors found a faster way to find such groups of three disks that don’t touch by using clever math and geometry ideas. They make the problem quicker to solve, especially when disks or their centers form certain shapes called convex arrangements. This work shows even small problems like groups of three have interesting patterns and can be solved efficiently.
Open → 2611.19592v1

Dynamic clustering keeps centers updated fast with limited changes

Dynamic $k$-Median with Worst-Case Update Time and Recourse

Abstract: We study fully dynamic metric $k$-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most $k$ centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with $\widetilde O(k)$ worst-case update time and $O((1+\logΔ)^3)$ worst-case center recourse, where $Δ$ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric $k$-means.

Thu 12 NovData Structures and Algorithms
The gist
The paper looks at how to quickly update group centers when points are added or removed from a space, like choosing store locations as customers come and go. The authors create a method that always keeps the number of centers small and close to optimal, while making only a few center changes each time. Their approach works reliably for any sequence of updates and runs efficiently even in the worst cases. They also adapt their method to a related grouping problem called k-means.
Open → 2611.17296v1

Improved efficient network design on planar graphs with small length slack

A Little Length Slack Goes a Long Way in Planar Length-Constrained Network Design

Abstract: Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. Algorithms that instead connect these pairs by paths of length at most $βh$ are said to have length slack $β$. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+ε$ and approximation ratios of $O(\log^2 k/ε)$ for directed Steiner tree and $O(\log^5 k/ε^2)$ for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/ε)$ approximation on planar graphs with length slack $6+ε$. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$.

Thu 12 NovData Structures and Algorithms
The gist
Designing networks that connect points with short paths can be very hard. The authors show that on flat (planar) layouts, allowing just a tiny bit of extra path length makes it much easier to find good network designs quickly. They created algorithms that nearly match the best possible solutions while only slightly increasing path lengths. They also prove it’s much harder to do this well on non-flat networks when the allowed path length increase is very small.
Open → 2611.17201v1

Improved coverage solutions with flexible center limits in distance problems

Nearly Optimal Dilation for Non-Uniform k-Center with Constant-Factor Budget Violation

Abstract: In Non-Uniform $k$-Center, we are given a metric space $(V,d)$ and $L$ levels of balls with prescribed radii $r_1 \ge \ldots \ge r_L$ and nonnegative integer budgets $k_1,\ldots,k_L$. The goal is to place at most $k_\ell$ centers of each level $\ell \in [L]$ in $V$ and minimize the dilation $λ$ such that the corresponding balls of radii $λr_1,\dots,λr_L$ cover $V$. While this problem admits no subexponential approximation factor unless P=NP, the picture changes drastically when additional centers are allowed. An $(α,β)$-bicriteria approximation to Smooth Non-Uniform $k$-Center covers $V$ with dilation $βλ_{\text{opt}}$ such that, for each $\ell \in [L]$, the number of centers of the first $\ell$ levels is at most $α$ times their total budget. For every fixed $\varepsilon>0$, we give a randomized $(1+\varepsilon,8+\varepsilon)$-approximation and a deterministic $(O_{\varepsilon}(1),2+\varepsilon)$-approximation, both running in polynomial time. Even for classical $k$-Center, obtaining an $(O(1),2-δ)$-approximation is NP-hard for every fixed $δ\in (0,1]$. Thus, our second result almost settles the optimal dilation when a constant-factor violation of the budget is allowed, unless P=NP. We combine a new primal-dual enumeration procedure with a simple bucketing argument that yields a new trade-off between the two approximation factors. It remains open whether there is a polynomial-time $(1+\varepsilon,2+\varepsilon)$-bicriteria approximation, which would almost match the classical $2$-approximation for $k$-Center.

Thu 12 NovData Structures and Algorithms
The gist
Some problems involve placing limited 'centers' on a map to cover all locations within certain distances. The authors study a complex version where centers can have different sizes and budgets. They show that by allowing a small, fixed increase in the number of centers, they can almost match the best possible coverage quality. Their methods work efficiently and clarify what can be achieved with slight relaxations in the rules.
Open → 2611.17100v1

New tight bounds improve estimating metric steiner tree costs

Tight Bounds for Sublinear Metric Steiner Tree

Abstract: In the metric Steiner tree problem we are given an $n$-point metric space $(V,w)$ and a set $T\subseteq V$ of terminals, and we seek the smallest weight $\mathrm{OPT}$ of a tree that spans $T$ and may use points of $V\setminus T$. We study sublinear algorithms in the distance-oracle model, where the algorithm knows $V$ and $T$ upfront and can query the distance function $w$. The objective is to estimate $\mathrm{OPT}$ while querying significantly fewer than $n^2$ distances. The minimum spanning tree on $T$ estimates $\mathrm{OPT}$ within a factor $2$, and its weight can be approximated with $\widetilde{O}(n)$ queries. The natural question that has been studied is therefore the query complexity of estimating $\mathrm{OPT}$ within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using $\widetilde{O}(n^{13/7})$ queries, and a lower bound of $\widetildeΩ(n^{6/5})$. Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to $\widetilde{O}(n^{5/3})$, and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to $\widetildeΩ(n^{7/5})$. In this work we settle the above question. We give an algorithm that estimates $\mathrm{OPT}$ within a factor $2-η_0$, for an absolute constant $η_0>0$, with query (and time) complexity $\widetilde{O}(n^{3/2})$. We also show that the exponent $3/2$ is tight.

Mon 9 NovData Structures and Algorithms
The gist
The problem involves finding the cheapest way to connect a special group of points with a tree, possibly using other points to save cost. The authors focus on estimating this cost quickly without checking every distance between points. Previous methods could get an estimate within twice the actual cost but required many distance checks. The authors present a method that estimates the cost slightly better than twice the actual cost using significantly fewer distance checks and prove this efficiency can’t be improved much further.
Open → 2611.11986v1

Hollow core fibers cut delay and power use in optical networks

When Less is More: Emerging Network-Wide Use Cases for Hollow-Core Fibers in Optical Networks [Invited]

Abstract: Hollow-Core Fiber (HCF) is emerging as a disruptive technology for next-generation optical networks, offering 30\% lower propagation latency than standard Single-Mode Fiber (SMF), record-low attenuation (0.05-0.1 dB/km), and nonlinearities reduced by three to four orders of magnitude. While the physical-layer benefits of HCF have been extensively demonstrated, recent industrial commitments by hyperscalers (e.g., Microsoft, Amazon) and the rapid maturation of nested antiresonant nodeless fibers (NANF) call for a systematic assessment of the impact of HCF at the network level. Building on a series of prior contributions, we overview four emerging network-wide use cases for the selective deployment of HCF in hybrid SMF/HCF networks: (i) latency-constrained Edge Data Center (edgeDC) consolidation; (ii) energy-efficient high-power amplification; (iii) capacity scaling via single-fiber bidirectional (BiDi) transmission; and (iv) coexistence of classical and quantum (QKD) channels. Consolidated results across realistic metro, national, and continental topologies convey a unifying message: in each use case, a selective HCF upgrade captures a significant share of the achievable benefit compared to a network overhaul. The required HCF budget is use-case-specific, i.e., 6-24\% of the total network fiber length for edgeDC consolidation (up to 50\% fewer edgeDCs), 40\% of the network links for QKD/classical coexistence (up to 38\% fewer quantum modules), and 40-60\% of the network links for energy-efficient capacity scaling via BiDi-HCF (up to 28\% lower network power per Tbps and 70\% more served traffic, at half the HCF strand count of a unidirectional HCF upgrade), whereas for energy-efficient high-power amplification the gain keeps growing with the HCF budget (up to 60\% lower network power per Tbps at the national scale) and what saturates is the benefit of increasing the EDFA output power.

Thu 5 NovEmerging TechnologiesNetworking and Internet Architecture
The gist
Optical networks use thin fibers to send data, but the usual fibers slow signals down and waste energy. The authors look at new hollow-core fibers that let light travel faster and with less energy loss. They find that using these fibers in specific parts of a network can reduce delays, save power, and improve capacity without replacing all the cables. This means networks can be better upgraded step-by-step rather than completely rebuilt.
Open → 2611.08389v1

Minimum sum-of-radii clustering solved exactly for any constant stability

Exact Sum-of-Radii Clustering under Any Constant Stability

Abstract: We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<γ<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $γ>1$, extending Gao and Reyzin's result for $γ\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,γ]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<γ<2$, our algorithm runs in $n^{O((γ-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $γ>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.

Mon 2 NovData Structures and Algorithms
The gist
Clustering groups data points based on distances, often by optimizing the shape or size of clusters. This paper studies a type of clustering called Minimum Sum-of-Radii (MSR), which aims to minimize the sum of cluster radii. The authors show that MSR can be solved exactly and efficiently when data distances meet a broad stability condition, improving on prior results that needed stronger assumptions. They also clarify that checking stability or verifying optimality under perturbations is computationally hard. This advances understanding of when clustering can be reliably and quickly found.
Open → 2611.03547v1

Exact minimum degree greedy outcomes found for interval graphs

Exact Tie-Breaking and Tight Degree Bounds for Minimum-Degree Greedy on Interval Graphs

Abstract: Minimum-degree greedy repeatedly selects a vertex of minimum current degree and deletes its closed neighborhood; let $B(G)$ and $W(G)$ be its largest and smallest output sizes over complete legal executions. Given a closed interval representation of an $n$-vertex graph, we compute both values and construct attaining executions in $O(n^3)$ time and $O(n^2)$ space using endpoint-window dynamic programming and legal interleaving. For interval graphs with $Δ(G)\le4$, we prove the tight bound $B(G)\ge3α(G)/4$ by reduction to unit interval graphs and induction with virtual boundary vertices. A connected unit interval family $J_t$ attains equality, with $B(J_t)=W(J_t)=3t$ and $α(J_t)=4t$. For each degree bound $d\ge5$, a degree-five family $H_t$ approaches the known $2/3$ lower bound, giving infimum $2/3$. Together with known optimal favorable tie-breaking for $d\le3$, these results determine the favorable guarantee for every degree bound.

Sun 1 NovData Structures and Algorithms
The gist
Finding the largest or smallest sets of points in a certain kind of overlapping interval graph can be tricky. This paper figures out exactly how well a simple method called minimum-degree greedy works when you pick points one-by-one by their smallest number of connections. The authors give a way to compute the best and worst results fast and prove tight limits on how small or large those sets can be depending on graph connections. They also show special families of graphs where these limits are met exactly.
Open → 2611.01796v1

Multi-robot coordination resilient to failures and communication breaks

Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization

Abstract: Multi-robot coordination is essential in applications such as coverage, target tracking, and information gathering, where robots must jointly select actions to maximize team performance. Submodular maximization provides an effective framework for such coordination, and resilient variants further account for robot failures or adversarial removals. However, existing methods typically overlook the impact of robot loss on the communication network, which may disconnect the surviving team and prevent continued coordination. To address this issue, we introduce Resilient $k$-Connected Submodular Maximization, which jointly considers task performance, resilience, and communication connectivity. The resulting feasible family is not a matroid, preventing the direct application of classical curvature-greedy guarantees. We overcome this challenge through a Menger-based connectivity reduction, a connectivity-aware greedy algorithm with a feasibility-preserving fallback, and a new curvature-based analysis that captures the cost of enforcing connectivity through a single factor $ρ$. Our method achieves a worst-case post-failure objective within a factor of $[\max(1-ν_f(\mathcal{I}),h(N,β))]^2 ρ\frac{1}{κ_f}(1-e^{-κ_f})$ of the optimal connectivity-respecting resilient assignment, while recovering the classical unconstrained guarantee in the appropriate limits. Experiments on multi-robot target tracking validate the proposed method and characterize the practical impact of connectivity constraints.

Fri 9 OctRoboticsMultiagent Systems
The gist
When teams of robots work together, they must both perform their tasks well and keep in touch with each other to coordinate. The authors looked at ways to plan robot actions so the team still works well even if some robots fail or lose contact. They developed a new mathematical approach that balances doing the job, surviving failures, and staying connected. Tests showed their method helps robot teams keep tracking targets effectively, even if some connections break.
Open → 2610.13049v1

New algorithm improves approximation for network design problems

An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest

Abstract: We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{Ω(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.

Wed 7 OctData Structures and Algorithms
The gist
This paper tackles the challenge of connecting certain groups of points in a network with as little cost as possible, known as the Steiner k-Forest problem. The authors developed an improved method that provides better solutions than previous approaches for large networks. They also show that making the solutions significantly better for some cases would be extremely difficult due to connections with another hard problem called Densest k-Subgraph. This work helps understand the limits of how efficiently these complex network problems can be approximated.
Open → 2610.09932v1

Agentic framework improves wireless network digital twin accuracy

Agentic Wireless Digital Twin Construction and Calibration Using Real-World Measurements

Abstract: Wireless digital twins (WDTs) are promising enablers for developing and evaluating AI-native radio access networks, yet constructing a high-fidelity WDT typically requires substantial manual effort to integrate heterogeneous information and infer unknown propagation-related parameters. This paper proposes Agentic WDT (AWDT), an end-to-end agentic framework for autonomous WDT construction and calibration using readily available environmental information and measurements readily obtainable from commercial smartphones. AWDT comprises three agents: EnvAgent constructs the propagation environment, OpAgent infers BS and sector configurations, and MatAgent calibrates radio material properties. The agents iteratively refine the WDT using discrepancies between LTE/NR reference signal received power (RSRP) measurements and ray-tracing predictions. Real-world experiments show that AWDT reduces the RSRP prediction MAE from 11.46 to 5.25 dB, demonstrating a substantial improvement in ray-tracing fidelity. Evaluation with an independent measurement system further demonstrates cross-device transferability with lightweight device-specific bias adaptation, highlighting the potential of agentic AI for scalable WDT construction and calibration with limited prior knowledge.

Thu 1 OctInformation Theory
The gist
Wireless digital twins are like virtual models of real-world wireless networks that help in testing and improving network designs. The authors developed a new system that uses smart agents to build and fine-tune these models automatically using data from everyday smartphones. Their approach dramatically improves the accuracy of predicting signal strength by reducing errors. This method also works well with different devices by adjusting for small biases, making it a practical tool for large-scale wireless network simulations.
Open → 2610.01437v1

Biplanar graphs with small independence number need at most nine colors

Biplanar graphs with independence number two are 9-colorable

Abstract: A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have chromatic number at least 10. Gethner and Sulanke asked in 2009 whether such a graph exists. We show that it does not, and more generally that every biplanar graph with independence number at most 2 is 9-colorable. The proof embeds a hypothetical counterexample in the union of two sphere triangulations, enumerates with SAT modulo symmetries the 3271 graphs that pass a necessary filter for the complement of such a union, and shows with a SAT solver that none of them is such a complement; a matching argument reduces the general statement to this computation and one further case on 18 vertices. The computational part of the proof, including the completeness of the enumeration and every refutation, is checked in Lean 4, assuming three classical facts about planar graphs. The Lean development, the SAT instances, and the enumeration certificates are available on Zenodo.

Wed 23 SeptLogic in Computer Science
The gist
This paper studies a type of graph made by combining two graphs that can be drawn without crossing lines. When coloring such graphs—assigning colors so that connected points differ—the question is how many colors are needed if no three points are all separate from each other (independence number 2). The authors prove that these graphs can always be colored with at most nine colors, resolving an open question. They reached this conclusion by combining mathematical reasoning with computer checks verified by formal proof software.
Open → 2609.28102v1

Moving geometric objects to ensure connected or dense intersection graphs

Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense

Abstract: In this paper, we study graph editing problems on geometric intersection graphs. For a tuple $\mathcal{S}=(S_1,\dots,S_n)$ of geometric objects in some Euclidean space, let $G_\mathcal{S}$ be their intersection graph. We study the problem of finding a tuple $D=(d_1,\dots,d_n)$ of movement vectors such that the resulting intersection graph $G_{\mathcal{S}+D}$ (after moving, for every $i \in \{1,\dots,n\}$, object $S_i$ by $d_i$) has a predefined property and the total movement distance $|D|$ is minimum. In the weighted version, we are also given a weight vector $w=(w_1,\dots,w_n)$ with positive entries, and the objective is to minimise the total weighted movement distance $|w \cdot D|$. We first consider the property locally dense, which we define as containment of a $k$-clique. Given $n$ weighted intervals, we solve the problem with respect to this property in $O(k^{1/3} n \log^{1+\varepsilon} n)$ time for any $\varepsilon>0$. We then consider $k$-connectivity for $1\le k \le n-1$. Given $n$ unweighted unit intervals, we solve the problem in $O(n^2 \log n)$ time and, for $k=1$, in $O(n\log n)$ time. For $k=1$, we prove strong NP-hardness on intervals of arbitrary length and on weighted unit disks (with only two distinct weights), and weak NP-hardness on weighted intervals (even when lengths equal weights).

Sat 19 SeptComputational GeometryData Structures and Algorithms
The gist
This paper looks at how to move shapes like intervals or disks just enough to make their overlaps form graphs with certain features, such as being connected or having a dense cluster of overlaps. The authors focus on minimizing the total movement needed to achieve these properties. They develop algorithms to solve this with different shapes and connectivity goals, and also show some problems are hard to solve efficiently. This research helps understand how to control overlaps by small adjustments efficiently.
Open → 2609.22958v1

Core membership testing for minimum-cost network spanning games

Core stability recognition for minimum-cost spanning tree games: Parameterized perspective

Abstract: Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds to a player and each edge has an associated cost~$w$. A distinguished vertex $s \in V(G)$ represents the supply or source. For any coalition of players $S$, the characteristic cost function $c(S)$ is defined as the minimum cost of a spanning tree with respect to $w$, connecting exactly the vertices in $S \cup \{s\}$. In this paper we study the computational complexity of deciding core membership for MSTG. In general, deciding whether a given allocation is in the core is \textsf{coNP}-hard~(Faigle et al.,International Journal of Game Theory,1997). We study the core recognition problem under the name {\sc MSTG Core Non-Membership}. We extend the hardness to graphs which are very close to being planar. On the positive side, we present several algorithmic results within the framework of parameterized complexity. We show that {\sc MSTG Core Non-Membership} is fixed-parameter tractable when parameterized by the support size of the allocation. Turning into structural parameters of graphs, we show that the problem admits an FPT algorithm parameterized by treewidth and signed neighborhood diversity. Last but not least, we investigate kernelization. While in general graphs, under standard complexity-theoretical assumptions, {\sc MSTG Core Non-Membership} does not admit a polynomial kernel parameterized by the vertex cover number, we design a cubic kernel in planar graphs. Furthermore, in general graphs, we obtain quadratic kernel for signed neighborhood diversity and linear kernel for the parameter feedback edge number.

Wed 16 SeptComputer Science and Game TheoryComputational Complexity
The gist
This paper looks at a problem where different players in a network share costs for connecting to a supply point through a cheapest possible tree of paths. The key question is how to decide if a specific way of sharing costs is stable—meaning no group of players wants to change it because they could do better on their own. The authors show that this decision is hard in general but find special ways to solve it efficiently by focusing on specific graph properties or how many players have non-zero cost shares. They also design smaller equivalent problems for some types of networks to speed up the process.
Open → 2609.18807v1

Strategyproof methods improve pathway building between blocked regions

Strategyproof Mechanisms for Connecting Impassable Regions

Abstract: We study strategyproof mechanisms for building a pathway between two regions of a line segment separated by an obstacle. Each of the $n$ agents has a private location within its region and may use either its original route to a facility or the new pathway, whose traversal cost is a fraction $k\in[0,1)$ of its length. We seek strategyproof (SP) and group-strategyproof (GSP) mechanisms that approximately minimize maximum cost or social cost. After characterizing optimal pathways for both objectives, we establish a tight deterministic maximum-cost approximation ratio of $\frac{2}{1+k}$ and a deterministic social-cost upper bound of $\frac{n}{1+k(n-1)}$, together with complementary lower bounds. Both upper bounds are achieved by GSP mechanisms. We then study randomized mechanisms under strategyproofness in expectation. A power-proportional mechanism achieves a social-cost approximation ratio at most $5$, independent of $n$ and $k$, with a tight guarantee of $3$ for this mechanism when $k=0$. We prove randomized lower bounds of $\frac{3+2k}{2+3k}$ for maximum cost and $\max\big\{1,\frac{285}{263+385k}\big\}$ for social cost, the latter for $n\ge7$. Finally, we improve several bounds for the real-line pathway model of [Chan and Wang, AAMAS 2023]. Our deterministic maximum-cost lower bound of $2$ matches the upper bound obtainable from [Qin, Fang, and Liu, COCOA 2024]. We strengthen the deterministic social-cost lower bound from $\frac32$ to $2$ under SP and to $\max\{2,n-1\}$ under GSP. For randomized social cost, we sharpen the guarantee of Chan and Wang's proportional mechanism from $6$ to $3$ and raise their lower bound from $1.02$ to $\frac{285}{263}\approx1.08365$ for $n\ge7$.

Tue 8 SeptComputer Science and Game Theory
The gist
This paper looks at how to build a route connecting two separated areas when there's an obstacle between them, with agents whose exact positions are private information. The challenge is to design systems that encourage truthful reporting of locations while keeping travel costs low, either for the worst-off agent or for everyone combined. The authors find best possible trade-offs for deterministic methods and also explore randomized approaches with guaranteed performance. They further improve known results from earlier research in this area.
Open → 2609.08488v1