Resource Reservation: No Greedy Approach?

Question

I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only active if they have all requested resources.

Instance: A set of processes P, a set of resources R, the set of resource requests for each process, and an int k. Question: Is it possible to allocate resources so that at least k processes are active at the same time?

My initial inclination was that a greedy approach makes sense here. Sort the jobs in increasing order of number of resources requested, then allocate resources to processes until all resources are allocated or all processes have been attempted to be scheduled, as below:

procedure reserve_resources(P, R, k):
  int jobs_active = 0;
  Order processes in ascending order of number of resources requested;
  for each process:
    if (all of the processes' requested resources are available):
      allocate resources to that process;
      jobs_active++;
    end if;
  end for;

  if (jobs_active >= k):
    return "YES";
  else:
    return "NO";
  end if;
end procedure;

I've come across an answer for this problem which shows NP-completeness by reducing Independent Set to this resource reservation problem. For the IS instance G = (V, E), it makes the set of resources equal to E, the set of process equal to V, and any edge incident to an vertex is a resource requested by that process. If k processes have disjoint resource requests, then the vertices corresponding to those processes form an independent set.

This reduction makes sense to me and I know that IS is NP. I believe that P != NP, and I certainly don't think I've just proven the opposite while working on homework in my undergrad algorithms class. But I also can't find a counterexample to the algorithm I've presented. My question is, where does this algorithm fail?

Answer 1

Your algorithm is correct when all resources are interchangeable. For example, the resources are 100 memory units.

However, it may not return the right result when the resources are not of the same kind. One way to find a counterexample is to search for counterexample of the greedy algorithm on the maximum independent set is to, uh, search online. One counterexample I found is the following, where vertex $C$ is selected first.

.

User j_random_walker proposed the following strategy to figure out a counterexample, where the tip in the last statement is added by me.

Figure out how to force your algorithm make the "wrong" choice in the first step: Since your algorithm always chooses the process with the fewest resource requests first, that means you have to design the problem instance so that this choice can only lead to suboptimal solutions. Work backwards to discover constraints: Clearly if the optimal solution has all 2 processes, then they can't have any conflicts, so any order of choosing them will give the same answer. So the smallest counterexample must have at least 3 processes. We will not consider processes that only request one resource; it cannot be wrong to included those processes.

Here is the smallest counterexample on which the greedy algorithm might fail, which has 3 processes and 4 resources. Process $P$ requests resources $a$ and $b$. Process $Q$ request $a$ and $c$. Process $R$ request $b$ and $d$. When the greedy algorithm select $P$ first, it cannot select any more process.

---

Exercise. Find a counterexample on which the greedy algorithm will always fail.