Jianer Chen
ABSTRACT
Improved randomized and deterministic algorithms are presented for PATH, MATCHING, and PACKING problems. Our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. For example, for the k-PATH problem, our randomized algorithm runs in time O(4kk3.42m) and space O(nklogk + m), improving the previous best randomized algorithm for the problem that runs in time O(5.44kkm) and space O(2kkn + m). To achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time O(4k+o(k)m) for the k-PATH problem, one of time O(2.803kk nlog2 n) for the 3-D MATCHING problem, and one of time O(43k+o(k)n) for the 3-SET PACKING problem. All these significantly improve previous best algorithms for the problems.
- Improved algorithms for path, matching, and packing problems
Recommendations
Improved deterministic distributed matching via rounding
AbstractWe present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a ...
Improved deterministic algorithms for weighted matching and packing problems
AbstractBased on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O∗(4(r−1)k+o(k)), improving the previous best upper bound O∗(4rk+o(k)). In particular, the ...
Randomized parameterized algorithms for $$P_2$$P2-Packing and Co-Path Packing problems
In this paper, we study the Parameterized $$P_2$$ P 2 -Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized $$P_2$$ P 2 -Packing problem, based on the structure analysis of the problem and using random partition technique, a ...
Comments