2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried comparing the result by your algorithm with the result of brute-force algorithm given some random small input? $\endgroup$ – Apass.Jack Dec 18 '18 at 6:09
  • $\begingroup$ Hint: There's a counterexample with 3 processes and 6 resources. 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 3 processes, then they can't have any conflicts, so any order of choosing them will give the same answer. So the optimal solution must have 2 processes... $\endgroup$ – j_random_hacker Dec 18 '18 at 13:03
2
$\begingroup$

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.

counterexample to greedy example on maximum independent set.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.