Browsing Computer Science and Automation (CSA) by Subject "Approximation Algorithms"
Now showing items 1-4 of 4
-
Algorithms for Geometric Packing and Covering Problems
We study two fundamental problems related to geometric packing and covering, and design algorithms with improved worst-case performance guarantees for them. These problems have numerous applications in resource allocation, ... -
Improved Algorithms for Variants of Bin Packing and Knapsack
We study variants of two classical optimization problems: Bin Packing and Knapsack. Both bin packing and knapsack fall under the regime of "Packing and Covering Problems". In bin packing, we are given a set of input items, ... -
New Algorithmic and Hardness Results in Learning, Error Correcting Codes and Constraint Satisfaction Problems
Approximation algorithms are a natural way to deal with the intractability barrier that is inherent in many naturally arising computational problems. However, it is often the case that the task of solving the approximation ... -
Robust Algorithms for recovering planted structures in Semi-random instances
In this thesis, we study algorithms for three fundamental graph problems. These are NP-hard problems which have not been understood completely as there is a signifiicant gap between the algorithmic and the hardness fronts ...