Seminars

View all Seminars  |  Download ICal for this event

Fast Algorithms for Max Cut on Geometric Intersection Graphs

Series: M.Tech (Research) Thesis Defence - ONLINE

Speaker: Mr. Utkarsh Joshi M.Tech (Research) student Dept. of CSA

Date/Time: Sep 26 10:30:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor: Prof. Rahul Saladi

Abstract:
In the max cut problem, given a graph, the goal is to partition the vertex set into two disjoint sets such that the number of edges having their endpoints in different sets is maximized. Max cut is an NP-hard problem. The seminal work by Goemans and Williamson gave an approximation algorithm for the max cut problem having an approximation ratio of 0.878. In this work, we design fast algorithms for max cut on geometric intersection graphs. In a geometric intersection graph, given a collection of n geometric objects as the input, each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. Since we are dealing with the geometric intersection graphs, which have more structure than general graphs, the following questions are of interest: 1. Are there special cases of geometric intersection graphs for which max cut can be solved exactly in polynomial time? 2. It can be shown that the random cut gives a 0.5 approximation for the max cut. Is it possible to design linear or near-linear time algorithms (in terms of n) and beat the 0.5 approximation barrier? The edge-set of the graph is not explicitly given as input; therefore, designing linear time algorithms is of interest. 3. Can an approximation factor better than 0.878 be obtained for the geometric intersection graphs? We obtain the following results: An exact and fast algorithm for laminar geometric intersection graphs. Our algorithm uses a greedy strategy. A fast algorithm is obtained by combining the properties of laminar objects with range searching data structures. An O(n log n) time algorithm with an approximation factor of 2/3 for unit interval intersection graphs. We decompose the unit intervals into several cliques, and based on the number of edges between adjacent cliques, we choose an appropriate partitioning strategy. An O(n log n) time algorithm with an approximation factor of 7/13 for unit square intersection graphs. We use the largest clique in the graph to beat the 0.5 approximation barrier. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_NDY1ZjkzYzEtMzEwMC00OGU5LTk2NDQtMDQ3ZDAzYmU0M2I2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22d71644d4-9e9d-48e9-ab41-3a147899b402%22%7d

Speaker Bio:

Host Faculty: