اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA note on hierarchical hubbing for a generalization of the VPN problem
46
0
0.0
(
0
)
تأليف
Neil Olver
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. The notion of hierarchical hubbing was introduced (in the narrow context of a specific robust network design question), by Olver and Shepherd [2010]. Hierarchical hubbing allows for routings with a multiplicity of hubs which are connected to the terminals and to each other in a treelike fashion. Recently, Frechette et al. [2013] explored this notion much more generally, focusing on its applicability to an extension of the well-studied hose model that allows for upper bounds on individual point-to-point demands. In this paper, we consider hierarchical hubbing in the context of a previously studied (and extremely natural) generalization of the hose model, and prove that the optimal hierarchical hubbing solution can be found efficiently. This result is relevant to a recently proposed generalization of the VPN Conjecture.
قيم البحث
اقرأ أيضاً
For a partial word $w$ the longest common compatible prefix of two positions $i,j$, denoted $lccp(i,j)$, is the largest $k$ such that $w[i,i+k-1]uparrow w[j,j+k-1]$, where $uparrow$ is the compatibility relation of partial words (it is not an equival
ence relation). The LCCP problem is to preprocess a partial word in such a way that any query $lccp(i,j)$ about this word can be answered in $O(1)$ time. It is a natural generalization of the longest common prefix (LCP) problem for regular words, for which an $O(n)$ preprocessing time and $O(1)$ query time solution exists. Recently an efficient algorithm for this problem has been given by F. Blanchet-Sadri and J. Lazarow (LATA 2013). The preprocessing time was $O(nh+n)$, where $h$ is the number of holes in $w$. The algorithm was designed for partial words over a constant alphabet and was quite involved. We present a simple solution to this problem with slightly better runtime that works for any linearly-sortable alphabet. Our preprocessing is in time $O(nmu+n)$, where $mu$ is the number of blocks of holes in $w$. Our algorithm uses ideas from alignment algorithms and dynamic programming.
We discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower boun
d of $Omega(log n)$ per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as the Christofides algorithm.
Recently, some authors started calling it Christofides-Serdyukov algorithm, pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukovs findings and a translation of his article from Russian into English.
The article presents a generalization of Sherman-Morrison-Woodbury (SMW) formula for the inversion of a matrix of the form A+sum(U)k)*V(k),k=1..N).
It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the non-trivial minimizer of a symmetric submodular function and solving t
he hypergraph minimum cut problem. This note contains these observations.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
