W01

Max Coloring: Background

In this problem we will study a multi-channel wireless mesh network architecture. Let $V_{N}$ be the set of mesh routers in a mesh network and $E_{N}$ be the set of pairs of mesh routers which can communicate directly. Each router is equipped with two network interface cards.

Each router is to be assigned at most two channels, so that every pair of routers that have a direct communication line have a common channel to transmit information on.

All our routers have a lot to discuss! So we want to open up as many channels as we can: the more channels we have, the less congestion we expect as network traffic ebbs and flows across these routers.

Assume that the mesh network $G := (V_{N}, E_{N})$ is a simple, connected, bipartite, and undirected graph. Let $ℓ$ denote the maximum number of channels that we can feasibly open up given the structure of $G$ .

Part 1. OPT and matchings

Suppose $G$ has a matching on $k$ edges. What can you say about $ℓ$ , the optimal solution? Check all true statements.

The claims being made below are to be checked only if they hold for all instances.

$ℓ ⩾ k$
$ℓ ⩾ k + 1$
$ℓ ⩽ k$
$ℓ ⩽ k / 2$

Part 2. OPT and vertex cover

Suppose $G$ has a vertex cover of size at most $t$ . What can you say about $ℓ$ , the optimal solution? Check all true statements.

The claims being made below are to be checked only if they hold for all instances.

$ℓ ⩾ t$
$ℓ ⩽ 2 t$
$ℓ ⩽ t + 1$
$ℓ ⩽ t$

Part 3. A 2-approximation

Describe an algorithm that, given $G$ as input, outputs a valid channel assignment with at least $ℓ / 2$ channels.

Hint: use the fact that $G$ is bipartite.

Parallel Universe Job Scheduling

We have $n$ jobs $J_{1}, \dots, J_{n}$ , and each job has a two-dimensional duration $⟨ p_{i}, q_{i} ⟩$ . We have $m$ machines that exist in two parallel universes $P$ and $Q$ .

When a job $J_{i}$ is executed on any machine, it consumes $p_{i}$ units of time in $P$ and $q_{i}$ units of time in $Q$ .

Our goal is to assign the jobs to the machines so that the maximum time to completion across both universes is as small as possible. In particular, let $σ : [n] \to [m]$ denote a schedule, where $σ (i)$ denotes the machine that $J_{i}$ is assigned to. Then the two-dimensional makespan of $σ$ is defined as:

$max_{1 ⩽ k ⩽ m} (max {\sum_{{i \in [n] | σ (i) = k}} p_{i}, \sum_{{i \in [n] | σ (i) = k}} q_{i}}),$

We update $σ$ by assigning $J_{t}$ to $k^{⋆}$ and move to the next iteration if $t < n$ .

and this is what we seek to minimize.

Part 1. Greedy Again - I

Consider the following greedy approach to this problem: process the jobs in the order they are given; $J_{1}, \dots, J_{n}$ .

To begin with, all machines have zero load in both universes and $σ : \emptyset \to [m]$ is the empty assignment.

In the $t^{t h}$ iteration ( $1 ⩽ t ⩽ n$ ), suppose our schedule so far is $σ : [t - 1] \to [m]$ . Consider:

$k^{⋆} := \argmin_{1 ⩽ k ⩽ m} (min {\sum_{{i \in [n] | σ (i) = k}} p_{i}, \sum_{{i \in [n] | σ (i) = k}} q_{i}}),$

which is to say, $k^{⋆}$ is the machine with the lowest load overall; where the load of a machine is interpreted as the smaller of the two loads (between the two universes).

We update $σ$ by assigning $J_{t}$ to $k^{⋆}$ and move to the next iteration if $t < n$ .

Is this a $2$ -approximation algorithm?

Part 2. Greedy Again - II

Consider the following greedy approach to this problem: process the jobs in the order they are given; $J_{1}, \dots, J_{n}$ .

To begin with, all machines have zero load in both universes and $σ : \emptyset \to [m]$ is the empty assignment.

In the $t^{t h}$ iteration ( $1 ⩽ t ⩽ n$ ), suppose our schedule so far is $σ : [t - 1] \to [m]$ . Consider:

$k^{⋆} := \argmin_{1 ⩽ k ⩽ m} (min {\sum_{{i \in [n] | σ (i) = k}} p_{i} + \sum_{{i \in [n] | σ (i) = k}} q_{i}}),$

which is to say, $k^{⋆}$ is the machine with the lowest load overall; where the load of a machine is interpreted as the smaller of the two loads (between the two universes).

Is this a $2$ -approximation algorithm?

Part 3. Do we have

3

-approximations?

Which of the following statements is true?

The first algorithm (from Part 1) is a $3$ -approximation algorithm for the parallel-universe scheduling problem.
The second algorithm (from Part 2) is a $3$ -approximation algorithm for the parallel-universe scheduling problem.