Algorithms in Facility Location

$(1)$ Let DOM represent the Dominating Set Problem and PM the p$-$median problem. Show that DOM $$p PM$.(2)$ An interval $[$a$,$b$]$ on the real line with a $$ b represents the set of real numbers x so that a $$ x $$ b$.$ A set of intervals is proper if no interval in the set is contained by any other interval in the set. A proper interval graph is the intersection graph of a set of proper intervals. Devise an efficient feasibility test algorithm for the discrete unweighted p$-$center problem in proper interval graphs. Every edge in this graph has a weight of $1.$ In the discrete version, centers can only be located at the vertices of the network. Hint: use the interval representation of the graph. $(3)$ Given a network represented by graph G $=($V$,$E$)$ with customers located at the vertices, with all vertex weights $=1($unweighted vertices$),$ and with positive edge lengths, the obnoxious p$-$center problem is defined as follows: find a set of p facilities in the network $($the facilities may be placed on the edges of the network$)$ so as to maximize the smallest distance from a customer to its closest facility, maxS$$G minv in V d$($v$,$S$).$ In addition, any two facilities must be located at a minimum distance equal to r from each other $($no two facilities must be at a distance smaller than r from each other$).$ Intuitively, we are locating obnoxious facilities and we want our customers to be as far as possible from the facilities placed. $($a$)$ Propose a polynomial time algorithm the the $1-$center obnoxious facility location prob lem on a path network. $($b$)$ Devise a feasibility test for the obnoxious p$-$center problem on a path network. More precisely, answer the following question: given a path network with edges assigned some positive length, values r$,$ p$,$ and a distance value $,$ is there a set of p centers on the path so that the cost of the obnoxious center is at least $?($c$)$ Design an algorithm to solve the obnoxious p$-$center problem on a path graph. Hint: search using the feasibility test. Think about how you maintain the set of distances that you will be searching on$.$ Analyze your algorithm