اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Systematic Approach to Bound Factor-Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems
42
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the Metric Facility Location Problem (MFLP) and to a generalization where the distance function is a squared metric. We call this generalization the Squared Metric Facility Location Problem (SMFLP) and prove that there is no approximation factor better than 2.04, assuming P $ eq$ NP. Then, we analyze the best known algorithms for the MFLP based on primal-dual and LP-rounding techniques when they are applied to the SMFLP. We prove very tight bounds for these algorithms, and show that the LP-rounding algorithm achieves a ratio of 2.04, and therefore has the best factor for the SMFLP. We use UPFRPs in the dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, improving some of the previous analysis for the MFLP.
قيم البحث
اقرأ أيضاً
External potentials play a crucial role in modelling quantum systems, since, for a given inter- particle interaction, they define the system Hamiltonian. We use the metric space approach to quantum mechanics to derive, from the energy conservation la
w, two natural metrics for potentials. We show that these metrics are well defined for physical potentials, regardless of whether the system is in an eigenstate or if the potential is bounded. In addition, we discuss the gauge freedom of potentials and how to ensure that the metrics preserve physical relevance. Our metrics for potentials, together with the metrics for wavefunctions and densities from [I. DAmico, J. P. Coe, V. V. Franca, and K. Capelle, Phys. Rev. Lett. 106, 050401 (2011)] paves the way for a comprehensive study of the two fundamental theorems of Density Functional Theory. We explore these by analysing two many- body systems for which the related exact Kohn-Sham systems can be derived. First we consider the information provided by each of the metrics, and we find that the density metric performs best in distinguishing two many-body systems. Next we study for the systems at hand the one-to-one relationships among potentials, ground state wavefunctions, and ground state densities defined by the Hohenberg-Kohn theorem as relationships in metric spaces. We find that, in metric space, these relationships are monotonic and incorporate regions of linearity, at least for the systems considered. Finally, we use the metrics for wavefunctions and potentials in order to assess quantitatively how close the many-body and Kohn-Sham systems are: We show that, at least for the systems analysed, both metrics provide a consistent picture, and for large regions of the parameter space the error in approximating the many-body wavefunction with the Kohn-Sham wavefunction lies under a threshold of 10%.
We present a general approach to sparse domination based on single-scale $L^p$-improving as a key property. The results are formulated in the setting of metric spaces of homogeneous type and avoid completely the use of dyadic-probabilistic techniques
as well as of Christ-Hytonen-Kairema cubes. Among the applications of our general principle, we recover sparse domination of Dini-continuous Calderon-Zygmund kernels on spaces of homogeneous type, we prove a family of sparse bounds for maximal functions associated to convolutions with measures exhibiting Fourier decay, and we deduce sparse estimates for Radon transforms along polynomial submanifolds of $mathbb R^n$.
A new framework for deriving equations of motion for constrained quantum systems is introduced, and a procedure for its implementation is outlined. In special cases the framework reduces to a quantum analogue of the Dirac theory of constrains in clas
sical mechanics. Explicit examples involving spin-1/2 particles are worked out in detail: in one example our approach coincides with a quantum version of the Dirac formalism, while the other example illustrates how a situation that cannot be treated by Diracs approach can nevertheless be dealt with in the present scheme.
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of th
e points in $P$ to the balls in $mathcal{B}$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(log |P|)$ even with $beta < 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$-approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$. In this current work, we show that it is possible to obtain an $O(1)$-approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$.
The uncapacitated facility location has always been an important problem due to its connection to operational research and infrastructure planning. Byrka obtained an algorithm that is parametrized by $gamma$ and proved that it is optimal when $gamma>
1.6774$. He also proved that the algorithm achieved an approximation ratio of 1.50. A later work by Shi Li achieved an approximation factor of 1.488. In this research, we studied these algorithms and several related works. Although we didnt improve upon the algorithm of Shi Li, our work did provide some insight into the problem. We also reframed the problem as a vector game, which provided a framework to design balanced algorithms for this problem.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
