Theoretical Computer Science - Design and analysis of algorithm (Exact/Approximation, Deterministic/Probabilistic), Markov Chains Monte Carlo methods.
-
A faster algorithm for finding optimal semi-matching
with Jittat Fakcharoenphol and Bundit Lekhanukit,
In preparation.
[view
abstract]
A {\em semi-matching} on a bipartite graph $G=(U\cup V,E)$ is a set of
edges $M\subseteq E$ such that each vertex in $U$ is incident to
exactly one edge in $M$. Harvey, Ladner, Lov\'{a}sz, and Tamir
consider the matching as an assignment for tasks in $U$ to machines in
$V$. This motivates the definition of the cost of a semi-matching $M$
to be the sum of delay for each task. They give an $O(mn)$ algorithm
based on the Hungarian algorithm for bipartite matching, where
$n=|U\cup V|$ and $m=|E|$. In this paper, we give a
divide-and-conquer algorithm which runs in time $O(m\sqrt{n}\log n)$.
We also consider the weighted version of the problem, i.e., when each
task has an associated weight. The cost of the semi-matching is thus
the sum of the product of the weight and the delay for each task.
This case is left openned in Harvey et al. We give an algorithm that
runs in time $O(nm\log^2 n)$, a running time which is only a
polylogarithmic factor slower than Edmonds-Karp and Tomizawa's
algorithms for the weighted bipartite matching problem. Our algorithm
for the weighted case uses parametric heaps, data structures commonly
used in computational geometry.
- Detecting and cleaning intruders in sensor networks
with Jittat Fakcharoenphol , Bundit Laekhanukit and
Poonna Yospanya,
National Comp. Sci. and /Eng. Conf. 2004 (NCSEC'04).
[view
abstract]
We view the problem of detecting and cleaning intruders in sensor
networks using mobile agents as a version of the graph searching
problem. The goal is to minimize the number of agents running at the
same time. Three scenarios are considered, each differs in the
relative power of the agents and the intruders. Our main idea is to
use breadth-first-search (BFS) trees to organize the search. In the case
where the intruder is most powerful, we search the graph by levels of the nodes
on the BFS tree. However, in the second case where the network is
configurable, the number of agents could be improved significantly if a good
subgraph can be found. This motivates us to define the Minimum Search
Number Spanning Tree problem, of which we also prove its hardness. We
however show that one can still use a BFS tree to get a good result.
In the last scenario where the intruder has no information on the
status of the agents, random walks are used. In each case, we prove
upper bounds on the number of agents and provide experiment results.
- A deterministic nearly linear-time algorithm for finding minimum cuts in planar graphs
with Parinya Chalermsook
and Jittat Fakcharoenphol,
SODA 2004
[view
abstract]
We present a simple deterministic O(n log2 n)-time divide-and-conquer algorithm for finding minimum cuts in planar graphs. This can be compared to a randomized algorithm for general graphs by Karger that runs in time O(m log3 n) and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time O(mn + n2 log n). We use shortest paths in the dual graphs to partition the problem, and use the relationship between minimum cuts in primal graphs and shortest paths in dual graphs to find minimum cuts that cross the partitions efficiently.