اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAsymptotic performance of the Grimmett-McDiarmid heuristic
160
0
0.0
(
0
)
تأليف
Yuval Filmus
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Grimmett and McDiarmid suggested a simple heuristic for finding stable sets in random graphs. They showed that the heuristic finds a stable set of size $simlog_2 n$ (with high probability) on a $G(n, 1/2)$ random graph. We determine the asymptotic distribution of the size of the stable set found by the algorithm.
قيم البحث
اقرأ أيضاً
We consider the {em vector partition problem}, where $n$ agents, each with a $d$-dimensional attribute vector, are to be partitioned into $p$ parts so as to minimize cost which is a given function on the sums of attribute vectors in each part. The pr
oblem has applications in a variety of areas including clustering, logistics and health care. We consider the complexity and parameterized complexity of the problem under various assumptions on the natural parameters $p,d,a,t$ of the problem where $a$ is the maximum absolute value of any attribute and $t$ is the number of agent types, and raise some of the many remaining open problems.
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there
always exists a coloring which achieves discrepancy 6sqrt{n}. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencers result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is truly constructive in that it does not appeal to the existential arguments, giving a new proof of Spencers theorem and the partial coloring lemma.
We develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition, and as a step in the argument we give a graph partitioning algorithm with expansion and minimum degree c
onditions on the subgraphs induced by each part. These results extend previous work of Jenssen, Keevash, and Perkins (2019) on the Potts model and related problems in expander graphs, and of Oveis Gharan and Trevisan (2014) on partitioning into expanders.
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be
the minimum number of leaves in the representing tree. We construct a fixed-parameter tractable algorithm testing isomorphism of chordal graphs with bounded leafage. The key point is a fixed-parameter tractable algorithm finding the automorphism group of a colored order-3 hypergraph with bounded sizes of color classes of vertices.
For every constant $d geq 3$ and $epsilon > 0$, we give a deterministic $mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $Theta(n)$ vertices that is $epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2sqr
t{d-1} + epsilon$ (excluding the single trivial eigenvalue of~$d$).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
