2020/07/20 by Saurabh Kumar, Kumar, S Anil, N. S. Narayanaswamy +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Smart Parking Systems Research #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2007.09849
openalex publication_date 2020/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we consider the restricted case of the problem and improve the current best approximation ratio by presenting a polynomial time 12-approximation algorithm using linear programming and semi-definite programming. Our algorithm starts by solving the configuration LP and uses the optimum value to get a 12-gap instance. This is then followed by the well-known clustering technique of Bansal and Sviridenko\citebansal. We then apply the analysis of Asadpour et al. \citeAFS,AFS2 to show that the clustered instance has an integer solution which is at least (1)/(6) times the best possible value, which was computed by solving the configuration LP. To find this solution, we formulate a problem called the Extended Assignment Problem, and formulate it as an LP. We then, show that the associated polytope is integral and gives us an fractional solution of value at least (1)/(6) times the optimum. From this solution we find a solution to a new quadratic program that we introduce to select one machine from each cluster, and then we show that the resulting instance has an Assignment LP fractional solution of value at least (1)/(6) times the optimum. We then use the well known rounding technique due to Bezakova and Dani \citebezakova on the 12-gap instance to get our 12-approximate solution.