{"id":432,"date":"2015-03-22T17:00:18","date_gmt":"2015-03-23T00:00:18","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=432"},"modified":"2015-03-22T17:00:18","modified_gmt":"2015-03-23T00:00:18","slug":"tutorial-8-problems","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/03\/22\/tutorial-8-problems\/","title":{"rendered":"Tutorial #8 Problems"},"content":{"rendered":"

This problem is based on 8.4 from the Kleinberg and Tardos textbook.<\/p>\n

Suppose you’re consulting for a group that manages a high-performance\u00a0real-time system in which asynchronous processes make use of shared\u00a0resources. Thus, the system has a set of n<\/em>\u00a0processes<\/i> and a set of\u00a0m<\/em>\u00a0resources<\/i>. Each process specifies a set of resources that it\u00a0requests to use. Each resource might be requested by many processes at\u00a0once, but it can only be used by a single process at a time.<\/p>\n

Your job is to allocate resources to processes that request them. If a\u00a0process is allocated all the resources it requests, then it is\u00a0active<\/i>; otherwise, it is blocked<\/i>. You want to perform the\u00a0allocation so that as many processes as possible are active.<\/p>\n

Thus, we phrase the Resource Reservation Problem<\/i> (RR) as follows:\u00a0Given a set of processes and resources, the set of requested resources\u00a0for each process, and a number k<\/em>, is it possible to allocate\u00a0resources to processes so that at least k<\/em>\u00a0processes will be active?<\/p>\n

    \n
  1. For this part and the next part only<\/b>, assume you do<\/b> have a\u00a0polynomial-time algorithm for RR. Give a polynomial-time algorithm\u00a0to determine the largest<\/b>\u00a0k<\/em>\u00a0for which you can allocate resources\u00a0to processes so that at least k<\/em>\u00a0processes will be active.<\/li>\n
  2. Still assuming you have a polynomial-time algorithm for RR, give a\u00a0polynomial-time algorithm to determine a maximum-size set of\u00a0processes that can be simultaneously active. (The specific\u00a0processes, not just how many there are.)<\/li>\n
  3. Now stop assuming you have a polynomial-time algorithm for RR, and\u00a0consider the following list of problems. For each problem either\u00a0give a polynomial-time algorithm or prove that the problem is\u00a0NP-complete. (In the former case, your “algorithm” may be a\u00a0reduction to another problem that you know can be solved in\u00a0polynomial time. Hint:<\/i> One of these can be solved in polynomial\u00a0time by reduction to the “maximum matching problem”, which can be\u00a0solved in polynomial time.)\n
      \n
    1. The general Resource Reservation Problem defined above.<\/li>\n
    2. The special case of the problem when k<\/em> = 2.<\/li>\n
    3. The special case of the problem when k<\/em> = 10.<\/li>\n
    4. The special case of the problem when there are two types of\u00a0resources\u2014say, robotic dogs and robotic cats\u2014and each\u00a0process requires exactly\u00a0one resource of each type. (In other\u00a0words, each process requires one specific robotic\u00a0dog and one specific robotic cat.)<\/li>\n
    5. The special case of the problem when each resource is requested\u00a0by at most two processes.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

      This problem is based on 8.4 from the Kleinberg and Tardos textbook. Suppose you’re consulting for a group that manages a high-performance\u00a0real-time system in which asynchronous processes make use of shared\u00a0resources. Thus, the system has a set of n\u00a0processes and a set of\u00a0m\u00a0resources. Each process specifies a set of resources that it\u00a0requests to use. Each […]<\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3426],"tags":[],"class_list":["post-432","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/432","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/comments?post=432"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/432\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=432"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=432"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=432"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}