اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNoisy source location on a line
97
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study the problem of locating the source of an epidemic diffusion process from a sparse set of sensors, under noise. In a graph $G=(V,E)$, an unknown source node $v^* in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $ein E$, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $sigma^2$. An algorithm then attempts to locate $v^*$ by picking sensor (also called query) nodes $s in V$ and being told the length of the shortest path between $s$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: static, in which all query nodes must be decided in advance, and sequential, in which each query can depend on the results of the previous ones. We characterize the query complexity when $G$ is an $n$-node path. In the static setting, $Theta(nsigma^2)$ queries are needed for $sigma^2 leq 1$, and $Theta(n)$ for $sigma^2 geq 1$. In the sequential setting, somewhat surprisingly, only $Theta(loglog_{1/sigma}n)$ are needed when $sigma^2 leq 1/2$, and $Theta(log log n)+O_sigma(1)$ when $sigma^2 geq 1/2$. This is the first mathematical study of source location under non-trivial amounts of noise.
قيم البحث
اقرأ أيضاً
In the streaming model, the order of the stream can significantly affect the difficulty of a problem. A $t$-semirandom stream was introduced as an interpolation between random-order ($t=1$) and adversarial-order ($t=n$) streams where an adversary int
ercepts a random-order stream and can delay up to $t$ elements at a time. IITK Sublinear Open Problem #15 asks to find algorithms whose performance degrades smoothly as $t$ increases. We show that the celebrated online facility location algorithm achieves an expected competitive ratio of $O(frac{log t}{log log t})$. We present a matching lower bound that any randomized algorithm has an expected competitive ratio of $Omega(frac{log t}{log log t})$. We use this result to construct an $O(1)$-approximate streaming algorithm for $k$-median clustering that stores $O(k log t)$ points and has $O(k log t)$ worst-case update time. Our technique generalizes to any dissimilarity measure that satisfies a weak triangle inequality, including $k$-means, $M$-estimators, and $ell_p$ norms. The special case $t=1$ yields an optimal $O(k)$ space algorithm for random-order streams as well as an optimal $O(nk)$ time algorithm in the RAM model, closing a long line of research on this problem.
When selecting locations for a set of facilities, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that takes local population densities into account. In particular, given $
k$ facilities to locate and a population of size $n$, we define the neighborhood radius of an individual $i$ as the minimum radius of a ball centered at $i$ that contains at least $n/k$ individuals. Our objective is to ensure that each individual has a facility within at most a small constant factor of her neighborhood radius. We present several theoretical results: We show that optimizing this factor is NP-hard; we give an approximation algorithm that guarantees a factor of at most 2 in all metric spaces; and we prove matching lower bounds in some metric spaces. We apply a variant of this algorithm to real-world address data, showing that it is quite different from standard clustering algorithms and outperforms them on our objective function and balances the load between facilities more evenly.
We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when
sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems. We show how to compute tasks in a noise-resilient manner over noisy beeping networks of arbitrary structure. In particular, we transform any algorithm that assumes a noiseless beeping network (of size $n$) into a noise-resilient version while incurring a multiplicative overhead of only $O(log n)$ in its round complexity, with high probability. We show that our coding is optimal for some tasks, such as node-coloring of a clique. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST($B$) model over a noisy beeping network. The simulation succeeds with high probability and incurs an asymptotic multiplicative overhead of $O(Bcdot Delta cdot min(n,Delta^2))$ in the round complexity, where $Delta$ is the maximal degree of the network. The overhead is tight for certain graphs, e.g., a clique. Further, this simulation implies a constant overhead coding for constant-degree networks.
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment
. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the clients location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log n_act / log log n_act)-competitive algorithm, where n_act is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log n/ log log n), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log m + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where m is number of points in the input metric and c is the capacity of any open facility.
We present an analysis of the co-added and individual 0.7-40 keV spectra from seven Suzaku observations of the Sy 1.5 galaxy NGC 5548 taken over a period of eight weeks. We conclude that the source has a moderately ionized, three-zone warm absorber,
a power-law continuum, and exhibits contributions from cold, distant reflection. Relativistic reflection signatures are not significantly detected in the co-added data, and we place an upper limit on the equivalent width of a relativistically broad Fe K line at EW leq 26 eV at 90% confidence. Thus NGC 5548 can be labeled an weak type-1 AGN in terms of its observed inner disk reflection signatures, in contrast to sources with very broad, strong iron lines such as MCG-6-30-15, which are likely much fewer in number. We compare physical properties of NGC 5548 and MCG-6-30-15 that might explain this difference in their reflection properties. Though there is some evidence that NGC 5548 may harbor a truncated inner accretion disk, this evidence is inconclusive, so we also consider light bending of the hard X-ray continuum emission in order to explain the lack of relativistic reflection in our observation. If the absence of a broad Fe K line is interpreted in the light-bending context, we conclude that the source of the hard X-ray continuum lies at <100 gravitational radii. We note, however, that light-bending models must be expanded to include a broader range of physical parameter space in order to adequately explain the spectral and timing properties of average AGN, rather than just those with strong, broad iron lines.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
