Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing the bounded subcomplex of an unbounded polyhedron
382
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study efficient combinatorial algorithms to produce the Hasse diagram of the poset of bounded faces of an unbounded polyhedron, given vertex-facet incidences. We also discuss the special case of simple polyhedra and present computational results.
rate research
Read More
Let $mathcal{P}$ be an $mathcal{H}$-polytope in $mathbb{R}^d$ with vertex set $V$. The vertex centroid is defined as the average of the vertices in $V$. We prove that computing the vertex centroid of an $mathcal{H}$-polytope is #P-hard. Moreover, we show that even just checking whether the vertex centroid lies in a given halfspace is already #P-hard for $mathcal{H}$-polytopes. We also consider the problem of approximating the vertex centroid by finding a point within an $epsilon$ distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an $mathcal{H}$-polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to emph{any} ``sufficiently non-trivial (for example constant) distance, can be used to construct a fully polynomial approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of $d^{{1/2}-delta}$ for any fixed constant $delta>0$.
We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvatal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.
Given a graph $G=(V,E)$ and a positive integer $tgeq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $Fsubseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $tgeq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^pcdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^pcdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut&Count technique, we give a randomized algorithm with runtime $4^pcdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
PT-symmetric scattering systems with balanced gain and loss can undergo a symmetry-breaking transition in which the eigenvalues of the non-unitary scattering matrix change their phase shifts from real to complex values. We relate the PT-symmetry breaking points of such an unbounded scattering system to those of underlying bounded systems. In particular, we show how the PT-thresholds in the scattering matrix of the unbounded system translate into analogous transitions in the Robin boundary conditions of the corresponding bounded systems. Based on this relation, we argue and then confirm that the PT-transitions in the scattering matrix are, under very general conditions, entirely insensitive to a variable coupling strength between the bounded region and the unbounded asymptotic region, a result that can be tested experimentally and visualized using the concept of Smith charts.
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
