We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables. The number of rational arithmetic operations and comparisons is polynomial in the dimensions and the encoding length of the constraint matrix, independently of the right-hand side,...
We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case ti...
For a matrix $A$ over a field of characteristic two, let $\Phi(A)$ be the sum of its permutation monomials indexed by odd permutations. Although determinant and permanent coincide in this characteristic, this parity sub-sum retains information that neither gives separately. We show that $\Phi(A)$ and all its first part...
We give a deterministic algorithm that computes the parity of the number of Hamiltonian cycles in an $n$-vertex directed graph in $O(n^4(3/2)^n)$ time and $O(n^2)$ bits of working space, improving the $O^*(\varphi^n)$ bound of Bj\"orklund and Husfeldt. Their local-degree formula reduces the problem to a weighted sum ov...
We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted...
We give a deterministic algorithm for the parity of the number of directed Hamiltonian cycles in an $n$-vertex digraph. For $n\geq 2$, the running time is $O^*((3/2)^n)$ and the space usage is $2^{O(n/\log n)}$. The construction starts from the local-degree identity of Bj\"orklund and Husfeldt. Their surviving terms ar...
Han-Qing Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
