More Like this

1. Optimal strategies for patrolling fences

   https://doi.org/10.4230/LIPIcs.ICALP.2019.144  

   Haeupler, Bernhard; Kuhn, Fabian; Martinsson, Anders; Petrova, Kalina; Pfister, Pascal (April 2019, International Colloquium on Automata, Languages and Programming)

   A classical multi-agent fence patrolling problem asks: What is the maximum length L of a line fence that k agents with maximum speeds v_1,..., v_k can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that L = alpha sum_{i=1}^k v_i for some efficiency alpha in [1/2,1). After a series of works [Czyzowicz et al., 2011; Dumitrescu et al., 2014; Kawamura and Kobayashi, 2015; Kawamura and Soejima, 2015] giving better and better efficiencies, it was conjectured by Kawamura and Soejima [Kawamura and Soejima, 2015] that the best possible efficiency approaches 2/3. No upper bounds on the efficiency below 1 were known. We prove the first such upper bounds and tightly bound the optimal efficiency in terms of the minimum speed ratio s = {v_{max}}/{v_{min}} and the number of agents k. Our bounds of alpha <= 1/{1 + 1/s} and alpha <= 1 - 1/(sqrt{k)+1} imply that in order to achieve efficiency 1 - epsilon, at least k >= Omega(epsilon^{-2}) agents with a speed ratio of s >= Omega(epsilon^{-1}) are necessary. Guided by our upper bounds, we construct a scheme whose efficiency approaches 1, disproving the conjecture stated above. Our scheme asymptotically matches our upper bounds in terms of the maximal speed difference and the number of agents used. A variation of the fence patrolling problem considers a circular fence instead and asks for its circumference to be maximized. We consider the unidirectional case of this variation, where all agents are only allowed to move in one direction, say clockwise. At first, a strategy yielding L = max_{r in [k]} r * v_r where v_1 >= v_2 >= ... >= v_k was conjectured to be optimal by Czyzowicz et al. [Czyzowicz et al., 2011] This was proven not to be the case by giving constructions for only specific numbers of agents with marginal improvements of L. We give a general construction that yields L = 1/{33 log_e log_2(k)} sum_{i=1}^k v_i for any set of agents, which in particular for the case 1, 1/2, ..., 1/k diverges as k - > infty, thus resolving a conjecture by Kawamura and Soejima [Kawamura and Soejima, 2015] affirmatively. 

   more » « less
2. Towards Efficiently Provisioning 5G Core Network Slice Based on Resource and Topology Attributes

   https://doi.org/10.3390/app9204361  

   Li, Xin; Guo, Chengcheng; Xu, Jun; Gupta, Lav; Jain, Raj (October 2019, Applied Sciences)

   null (Ed.)

   Efficient provisioning of 5G network slices is a major challenge for 5G network slicing technology. Previous slice provisioning methods have only considered network resource attributes and ignored network topology attributes. These methods may result in a decrease in the slice acceptance ratio and the slice provisioning revenue. To address these issues, we propose a two-stage heuristic slice provisioning algorithm, called RT-CSP, for the 5G core network by jointly considering network resource attributes and topology attributes in this paper. The first stage of our method is called the slice node provisioning stage, in which we propose an approach to scoring and ranking nodes using network resource attributes (i.e., CPU capacity and bandwidth) and topology attributes (i.e., degree centrality and closeness centrality). Slice nodes are then provisioned according to the node ranking results. In the second stage, called the slice link provisioning stage, the k-shortest path algorithm is implemented to provision slice links. To further improve the performance of RT-CSP, we propose RT-CSP+, which uses our designed strategy, called minMaxBWUtilHops, to select the best physical path to host the slice link. The strategy minimizes the product of the maximum link bandwidth utilization of the candidate physical path and the number of hops in it to avoid creating bottlenecks in the physical path and reduce the bandwidth cost. Using extensive simulations, we compared our results with those of the state-of-the-art algorithms. The experimental results show that our algorithms increase slice acceptance ratio and improve the provisioning revenue-to-cost ratio. 

   more » « less
3. The slice spectral sequence for a motivic analogue of the connective K(1)$K(1)$‐local sphere

   https://doi.org/10.1112/plms.70006  

   Kong, Hana Jia; Quigley, J D (November 2024, Proceedings of the London Mathematical Society)

   Abstract We compute the 2‐adic effective slice spectral sequence (ESSS) for the motivic stable homotopy groups of , a motivic analogue of the connective ‐local sphere over prime fields of characteristic not two. Together with the analogous computation over algebraically closed fields, this yields information about the motivic ‐local sphere over arbitrary base fields of characteristic not two. To compute the spectral sequence, we prove several results that may be of independent interest. We describe the ‐differentials in the slice spectral sequence in terms of the motivic Steenrod operations over general base fields, building on analogous results of Ananyevskiy, Röndigs, and Østvær for the very effective cover of Hermitian K‐theory. We also explicitly describe the coefficients of certain motivic Eilenberg–MacLane spectra and compute the ESSS for the very effective cover of Hermitian K‐theory over prime fields. 

   more » « less
4. Hamiltonicity of random graphs in the stochastic block model

   https://doi.org/10.1137/19M1296069  

   Anastos, Michael; Frieze, Alan; Gao, jane (April 2021, SIAM journal on discrete mathematics)

   We study the Hamiltonicity of the following model of a random graph. Suppose that we partition $[n]$ into $$V_1,V_2,\ldots,V_k$$ and add edge $$\{x,y\}$$ to our graph with probability $$p$$ if there exists $$i$$ such that $$x,y\in V_i$$. Otherwise, we add the edge with probability $$q$$. We denote this model by $$\G(n, p,q)$$ and give tight results for Hamiltonicity, including a critical window analysis, under various conditions. 

   more » « less
5. Improved simultaneous multislice cardiac MRI using readout concatenated k‐space SPIRiT (ROCK‐SPIRiT)

   https://doi.org/10.1002/mrm.28680  

   Demirel, Omer Burak; Weingärtner, Sebastian; Moeller, Steen; Akçakaya, Mehmet (February 2021, Magnetic Resonance in Medicine)

   PurposeTo develop and evaluate a simultaneous multislice (SMS) reconstruction technique that provides noise reduction and leakage blocking for highly accelerated cardiac MRI. MethodsReadOutConcatenatedk‐space SPIRiT (ROCK‐SPIRiT) uses the concept of readout concatenation in image domain to represent SMS encoding, and performs coil self‐consistency as in SPIRiT‐type reconstruction in an extended k‐space, while allowing regularization for further denoising. The proposed method is implemented with and without regularization, and validated on retrospectively SMS‐accelerated cine imaging with three‐fold SMS and two‐fold in‐plane acceleration. ROCK‐SPIRiT is compared with two leakage‐blocking SMS reconstruction methods: readout‐SENSE‐GRAPPA and split slice–GRAPPA. Further evaluation and comparisons are performed using prospectively SMS‐accelerated cine imaging. ResultsResults on retrospectively three‐fold SMS and two‐fold in‐plane accelerated cine imaging show that ROCK‐SPIRiT without regularization significantly improves on existing methods in terms of PSNR (readout‐SENSE‐GRAPPA: 33.5 ± 3.2, split slice–GRAPPA: 34.1 ± 3.8, ROCK‐SPIRiT: 35.0 ± 3.3) and SSIM (readout‐SENSE‐GRAPPA: 84.4 ± 8.9, split slice–GRAPPA: 85.0 ± 8.9, ROCK‐SPIRiT: 88.2 ± 6.6 [in percentage]). Regularized ROCK‐SPIRiT significantly outperforms all methods, as characterized by these quantitative metrics (PSNR: 37.6 ± 3.8, SSIM: 94.2 ± 4.1 [in percentage]). The prospectively five‐fold SMS and two‐fold in‐plane accelerated data show that ROCK‐SPIRiT and regularized ROCK‐SPIRiT have visually improved image quality compared with existing methods. ConclusionThe proposed ROCK‐SPIRiT technique reduces noise and interslice leakage in accelerated SMS cardiac cine MRI, improving on existing methods both quantitatively and qualitatively. 

   more » « less