Faster Deterministic Algorithms for Packing, Matching and $t$-Dominating Set Problems

Abstract

In this paper, we devise three deterministic algorithms for solving the $m$-set $k$-packing, $m$-dimensional $k$-matching, and $t$-dominating set problems in time $O^{\ast }(5.44^{mk})$, $O^{\ast }(5.44^{(m-1)k})$ and $O^{\ast }(5.44^t)$, respectively. Although recently there has been remarkable progress on randomized solutions to those problems, our bounds make good improvements on the best known bounds for deterministic solutions to those problems.

ISAAC13 Submission. arXiv admin note: substantial text overlap with arXiv:1303.0478

References in corpus (1)

• Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

Cited by in corpus (1)

• On local search and LP and SDP relaxations for k-Set Packing