اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFooling Sets and the Spanning Tree Polytope
160
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is $Omega(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.
قيم البحث
اقرأ أيضاً
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best know
n lower bound is the trival (dimension) bound, $Omega(n^2)$, the best known upper bound is the extended formulation by Wong (1980) of size $O(n^3)$ (also Martin, 1991). In this note we give a nondeterministic communication protocol with cost $log_2(n^2log n)+O(1)$ for the support of the spanning tree slack matrix. This means that the combinatorial lower bounds can improve the trivial lower bound only by a factor of (at most) $O(log n)$.
An $ntimes n$ matrix $M$ is called a textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,ell} M_{ell,k} = 0$ for every $k e ell$. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that $n le (mbox{rk} M)^2$,
regardless of over which field the rank is computed, and asked whether the exponent on $mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = binom{mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(mbox{rk} M)^2$.
Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex
in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces.
We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(mathrm{tw}(G) + log n)}$, where $mathrm{tw}(G)$ is the treewidth of $G$. Our main result is that this bound is tight for graphs contained in minor-closed classes.
An ntimes n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k e ell we have M_{k,ell} M_{ell,k} = 0. Dietzfelbinger, Hromkoviv{c}, and Schnitger (1996) showed that n le (rk M)^2, regardless of
over which field the rank is computed, and asked whether the exponent on rk M can be improved. We settle this question for nonzero characteristic by constructing a family of matrices for which the bound is asymptotically tight. The construction uses linear recurring sequences.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
