PhD Oral Exam - Ali M. Lavasani, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

This thesis explores several problems in computational geometry and online algorithms, focusing on efficient algorithms for geometric optimization and real-time decision-making. We begin by addressing the offline computational geometry problem of the Maximum Weighted Convex Polytope (MWCP), followed by two online algorithmic problems: Online Non-Crossing Matching and Online Interval Scheduling.

In the MWCP problem, the goal is to find a convex polytope within a set of n weighted (positive and negative) points in R^d that maximizes the total weight of points inside or on the boundary. We present a new simple algorithm for the two-dimensional case, achieving the same time complexity of O(n^3) as previous methods. We also prove that MWCP is NP-hard in dimensions three or higher, even when weights are restricted to +1 and -1, and that in dimensions four or higher, the problem is NP-hard to approximate within a factor of n^{1/2-epsilon}.

We next focus on the Online Non-Crossing Matching problem, where points arrive sequentially in the plane and must be irrevocably matched to previously arrived points such that the resulting matched pairs form non-crossing line segments. We introduce the weighted version of this problem, aiming to maximize the total weight of matched pairs. We show that deterministic algorithms can have arbitrarily bad competitive ratios due to adversarial weight assignments. To address this, we consider weights within the range [1, U] and provide an algorithm with a competitive ratio of Omega (2^{-2 sqrt{ log U }}), along with an upper bound of O(2^{-sqrt{log U}}) for any deterministic algorithm. In the setting that allows revoking, we develop an algorithm that achieves a competitive ratio of approximately 0.28, and prove that no deterministic algorithm can exceed a competitive ratio of 2/3, even in the unweighted case. Additionally, we propose a randomized algorithm with a competitive ratio of 1/3, and show that no randomized algorithm can surpass a competitive ratio of 8/9 in the unweighted case.

We also study the advice complexity of this problem. We establish a lower bound of (n/3) - 1 on the advice complexity and provide an algorithm that uses approximately 2n bits of advice, matching log C_n, where C_n is the n th Catalan number. Furthermore, we derive a lower bound on the advice complexity required to achieve a competitive ratio in (16/17, 1). In the bichromatic version of this problem, where a set of n blue points are given offline and red points arrive online to be matched only to blue points, we correct previous errors in the literature and establish a lower bound of log C_n on the advice complexity. We also present an algorithm that uses log C_n bits of advice when points arrive in convex position.

In the final part, we consider the Online Interval Selection problem when the interval graph of the input is a simple path, allowing revoking of previous decisions. We show that under the random-order model, a deterministic memoryless algorithm achieves a competitive ratio of approximately 0.78. We also established an upper bound of 3/4 for any deterministic revoking algorithm on a simple chain in the adversarial model, and a lower bound of n/4 for the advice complexity of Online Interval Selection, marking the first lower bound for this problem.

Throughout this work, we develop novel algorithmic techniques, establish tight complexity bounds, and provide new insights into advice complexity for key problems in computational geometry and online algorithms. These contributions aim to advance the theoretical foundations of these fields and have potential applications in real-time systems and geometric data analysis.