Ph.D. Thesis. Supervisor: Uri Feige.
Many important optimization problems are known to be NP-hard. That is, unless $\P=\NP$, there is no polynomial time algorithm that optimally solves these problems on every input instance. We study algorithmic ways for ``coping'' with NP-hard optimization problems.
One possible approach for coping with the NP-hardness is to relax the requirement for exact solution, and devise approximation algorithms, i.e. efficient algorithms that produce a solution that is guaranteed to be nearly optimal. In the last decade, our understanding of many NP-hard optimization problems was greatly improved, both from the direction of approximation algorithms and from the direction of hardness of approximation. However, there is still a large gap in our understanding of the approximability of several fundamental problems.
A notable example is the minimum bisection problem, that requires to find in a graph a minimum-cost cut that partitions the vertices into two equal-size sets. This problem has applications both in theory and in practice. The seminal work of Leighton and Rao (1988) was largely motivated by this problem, and led to algorithms with approximation ratio $O(\log n)$ for several related problems. However, prior to our work no sublinear (in $n$) approximation ratio was known for this problem, and its approximability is a famous open problem.
We significantly improve the known approximation ratio for minimum bisection. Our algorithms achieve an approximation ratio $O(\log^2 n)$, which is ``in the same ballpark'' as the current approximation ratios for many related problems.
Another approach for coping with the NP-hardness is to relax the requirement for worst-case analysis, and consider instead heuristic algorithm that are successful on average-case input instances. One main difficulty in providing rigorous analysis of heuristics lies in realistically modeling average-case instances. Consider for example the hidden clique problem. In a random model for the problem, a random graph on $n$ vertices is chosen (i.e. $G_{n,1/2}$) and then a clique of size $k$ is randomly placed in the graph, and the goal is to find the planted clique in the graph. A semi-random model may extend this random model by allowing an adversary to remove any edge that is not inside the planted clique. We devise for the hidden clique problem a heuristic that is based on the Lovasz theta function, a well-known semidefinite programming relaxation of maximum clique. Our heuristic is successful in the semi-random model when $k\ge \Omega(\sqrt{n})$. In contrast, previous heuristics have similar success in the random model but fail in the semi-random model. We also study relaxations that are stronger than the Lovasz theta function, namely those obtained by the ``lift-and-project'' method of Lovasz and Schrijver (1991). We show that on a random graph $G_{n,1/2}$ the value of these stronger relaxations is comparable to the theta function, and hence they do not extend our heuristic mentioned above to a planted clique of smaller size $k=o(\sqrt{n})$.
M.Sc. Thesis. Supervisor: Uri Feige.
Hot-potato routing is a particular form of routing in a synchronous network of processors, which makes no use of buffers at intermediate nodes. Packets must keep moving in the network (possibly deflected to ``bad'' directions), giving rise to the term ``hot-potato''. Simple hot-potato algorithms are interesting for both practical and theoretical reasons.
We analyze the worst case performance of some simple hot-potato routing algorithms. For example, we show that any ``minimum advance'' algorithm cannot livelock on a tree network, and present a deterministic algorithm for general graphs, inspired by random walks.
One of our main topics studies an algorithm for the mesh based on selecting a small number of Hamiltonian paths, such that vertices that are close together on the mesh are also close together on at least one of these paths. Based on these families of Hamiltonian paths, routing between vertices is achieved in time that depends only on the distance between these vertices, regardless of the size of the whole mesh.
This framework of mapping meshes to several Hamiltonian paths may be of independent interest, and indeed we demonstrate its relevance to the construction of hash functions.