Algorithmic Methods: Optimal Group Assignment, MAX-SAT Approximation, And Task Scheduling.pdf

Summary

Instructions: Solve 4 out of the 5 questions. Each question is worth a specific number of points as indicated. Write concise but complete answers, adhering to the page limits provided.

Assumptions: All algorithms are given optimal access to input data and standard mathematical tools unless otherwise specified.

1. Agent Weight Assignment (n groups)

(a) Optimal Solution Structure: We prove that an optimal solution exists where at most n groups have positive weights. This is because we can always distribute the demand of each agent among these groups while ensuring no group exceeds its capacity.

(b) Polynomial Time Solution Value: The optimal value can be found in polynomial time by greedily forming groups and assigning weights based on agent demands, minimizing the total weight.

(c) Restricted Grouping: With the additional constraint that groups cannot contain both agents 2i and 2i-1 for any 1 ≤ i ≤ n/2, the optimal solution value remains unchanged (same as (b)) but requires a modified grouping strategy to satisfy the new rule.

2. MAX-SAT Approximation with LP and Randomized Rounding

(a) 3/4-Approximation: We demonstrate that random rounding of variables according to a specific probability distribution results in a solution achieving at least 3/4 of the optimal MAX-SAT value. This is proven using mathematical bounds on the rounding probabilities.

(b) Deterministic Approximation: A deterministic algorithm can be derived from the randomized one by carefully selecting thresholds for variable assignment based on the LP solution.

3. Task Scheduling (5-Approximation)

Design a greedy algorithm that selects tasks iteratively based on their width-to-value ratio, prioritizing those with the highest ratios. This ensures a feasible solution with maximum total value while adhering to the interval constraints.

4. Job Shop Scheduling (1/2 Approximation)

(a) Integer LP Formulation: Formulate the problem as an integer linear program, considering job-machine assignments and load constraints. Relax the integer constraints for easier optimization.

(b) Load Bounded Rounding: Round the relaxed solution to an integer assignment while ensuring the maximum load on any machine is at most twice the optimal load (2T). This involves selecting jobs with fractional assignments as leaves in the tree.

(c) 1/2 Approximation: Utilize a combination of greedy and rounding techniques to achieve a 1/2 approximation, maintaining a maximum load of at most T.

5. Graph Routing (1+ε Approximation)

(a) Integer LP Formulation: Create an integer linear program that considers request routing while respecting edge capacities. Relax the integer constraints for polynomial-time optimization.

(b) Rounding and Approximation: Apply a rounding technique, leveraging the Chernoof bound, to convert the relaxed solution into an integer assignment. This guarantees a (1 + ε)-approximation of the optimal solution value.