| Title | : | Parameterized Complexity Results on Santa Claus Problem and Makespan Minimization Problem |
| Speaker | : | Anil Kumar S (IITM) |
| Details | : | Thu, 27 Jun, 2024 10:00 AM @ SSB-334 |
| Abstract: | : | Santa Claus Problem and Makespan Minimization Problem are two well-known NP-hard problems whose fixed parameter tractability is not known for several common parameters. In Santa Claus Problem, a given set of jobs with predefined job sizes are to be allocated among a set of machines in such a way as to maximize the minimum of the total job sizes of all the machines. In Makespan Minimization Problem, a given set of jobs with predefined processing times are to be allocated among a set of machines in such a way as to minimize the maximum of the total processing times of all the machines. In this work, we study the parameterized complexity of the two problems when parameterized by the parameters in the set {number of machines, instance treewidth (treewidth of the natural bipartite graph representation of the input instance), target output value, maximum job size / maximum processing time}. We prove the W[1]-hardness of the two problems under the combined parameters {number of machines, instance treewidth} and {target output value, maximum job size/maximum processing time}. Our results also show that both problems are fixed parameter tractable when combining target output value with any one parameter in the set {number of machines, instance treewidth}. |
