AMS 553.766: Combinatorial Optimization Midterm, Spring 2022

N = {0, 1, 2, ...} will denote the set of natural numbers.

1.  (20 pts) We say that a set X S Rn  is bounded if and only if there exists a number M > 0 such that X S {x e Rn  : _M s xi  s M   Vi = 1, . . . , n}.

Let P = {x e Rn  : Ax s b} where A is an m x n matrix and b e Rm  and assume that P is nonempty.  Define the set C := {r e Rn  : Ar s 0}.  Show that P is bounded if and only if C = {0}.

[Hint:  P is bounded if and only if the linear programs max{xi  : Ax s b} and max{_xi  : Ax s b} have finite values for all i = 1, . . . , n.]

2.  Game of Slither. The game of Slither is played on a graph G = (V, E) between two players. The players, called First and Second, play alternately, with First playing first.  At each step the player whose turn it is chooses a previously unchosen edge. The only rule is that at every step the set of all chosen edges forms a simple path (i.e., a path with no repeated vertices). The loser is the first player unable to make a legal play at his or her turn.

(i)  (5  pts) Show that if G has a perfect matching  (a matching which leaves no vertex exposed), then First has a winning strategy.

(ii)  (10 pts) Suppose First’s first move is an edge uv such that u is an inessential vertex of

G.  Show that Second can now force a win.  [Recall that a vertex is inessential if there exist a maximum matching that leaves this vertex exposed]

3.  (20 pts) We consider the problem of scheduling a set J of jobs on M e N uniform parallel machines. Each job j e J has a processing requirement pj  e N which denotes the number of days needed to process the job on any one of the machines. Each job also comes with a release date rj  e N, representing the beginning of the day the job j becomes available for processing, and a due date dj  > rj  + pj, representing the beginning of the day by the end of which job j must be completed (dj  is also a natural number). We start our count of days from day 0. Any machine can process only one job in a single day, and any job can be processed by at most one machine on a given day. However, we allow preemptions, i.e., we can interrupt a job and process it on different machines on different days (recall that all machines are uniform, i.e., have the same processing speed).  The scheduling problem is determine if there exists a feasible schedule of jobs assigned to machines on different days such that all jobs are processed in their respective windows.

Give an algorithm that decides in polynomial time whether a feasible schedule exists or not.   The algorithm should be polynomial time in the data, that is polynomial in IJI, M,    joJ(log rj+ log dj + log pj).

[Hint:  The following construction could be useful:  Arrange the numbers rj, dj  in ascending order and create 2IJI _ 1 intervals of consecutive days defined by these numbers.]

4.  (20 pts) (Linear regression with different objectives) In linear regression, we have a

bunch of labeled data points z 1 , . . . , zk  e Rn  with real valued labels y1 , . . . , yk.  We want to fit the best linear function to this labeled data.  More precisely, we want to find parameters β = (β1 , . . . , βn) so as to minimize the errors Iyj  _     βizi(j) I.  The typical objective is the sum of the squares of the errors, i.e., we wish to minimize     j(k)=1 (yj  _     βizi(j))2 .  Suppose we are interested in the following variant:

Firstly, we don’t want to allow arbitrary values of the parameters; we want more controlled regression.  Suppose for each parameter βi, we have certain preset upper and lower bounds ui  and ei  respectively that we want the parameter to lie within. Also, instead of minimizing the sum of squares, suppose we want to minimize the sum of the absolute values, i.e., min- imize     j(k)=1 Iyj  _     βizi(j) I subject to these bound constraints on the parameter values (e1 minimization).