Authors: Romain Cosson, Yichen Huang, Michael Mitzenmacher, Ali Vakilian
Organizations: Computer Science Department, Courant Institute, New York University. · John A. Paulson School of Engineering and Applied Science, Harvard University. · Rutgers University.
We study collective tree exploration with subtree-size predictions. In this problem, a team of k mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex u is discovered, the team receives a prediction n^u of the number of nodes nu in the subtree rooted at u. We provide algorithmic guarantees under two error measures: the maximum error E=maxu∣nu−nu∣ and the multiplicative distortion μ=(maxunu/nu)(maxunu/nu). For the maximum error, we present a deterministic algorithm that explores any tree with n nodes and depth D in O(OPT+E) rounds, where OPT=Θ(n/k+D) is the offline benchmark, and we show that there is no deterministic algorithm that admits an O(OPT)+o(E) guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in O(min{μlogk,μloglogk+μ1.5}), where the O(⋅) may hide logarithmic factors in μ.
Figures & tables
Figure 1: Seed and sweep. In the sweep panel, each edge is styled according to the first robot that traverses it: solid orange for s1 , dashed blue for s2 , and dash-dotted purple for s3 .
Figure 2: A τ -skeleton and the threshold components exposed after lowering the threshold to τ′<τ . Bold red vertices are frontier vertices of Sτ ; bold white vertices are frontier vertices of Sτ′ . The orange boxes C1,C2,C3 are the threshold components of τ,τ′ .
Method
Threshold evolution
Exploration within a layer
Competitive ratio
Baseline ( Section 4.1 )
Halve each time
One robot per component
O(μlogk)
Adaptive teams ( Section 4.2 )
Halve each time
Adaptive team sizes 1,2,4,…,Θ(μ) .
O(μlogk)
Aggressive exploration ( Section 4.3 )
Quota-dependent large jumps
PowerScatter then adaptive tail.
O(μloglogk+μ3/2)
Table 1: Three instantiations of the skeleton framework.
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 3 and the communication range is 1.
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret O(nlog2n), using O(n2logn) arithmetic operations and O(n) stored entries. The exact minimax rate remains open.
Marek Gałązka, Hanna Wdowicka
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland · Department of Statistics, Poznań University of Economics and Business, Poznań, Poland
The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.