2
$\begingroup$

I have this following question. It is a question I got from past tests in a course called advanced algorithms. It is not a homework question I just want to understand the solution.

The question goes as follows: We are given a graph $G=(V,E)$ with a source node $s\in V$ and a value $d_v\geq 0$ for every $v\in V$, and with weight=capacity $c_e\geq 0$ for every edge $e\in E$. In this question when referring to a subset of V the meaning is a set $S \subseteq V$ s.t. $S \neq \emptyset,V$, and $P_v$ is a path in $G$ from the source node $s$ to $v$.

In the dual Problem there is a variable $y_S$ for each subset of nodes/vertices and a variable $z_{P_v}$ for each path $P_v$ in the Graph. The objective of the dual problem is to maximize the following expression:

$\sum\limits_{S \subseteq V} y_S + \sum\limits_{paths\\P_v} d_vz_{P_v}$

The constrains of the dual problem is that for every edge $e\in E$ must hold the following inequality:

$\sum\limits_{S \subseteq V\\s.t. e\in \partial_e(S)} y_S + c_e(\sum\limits_{paths\\e\in P_v} z_{P_v})\leq c_e$

The question has 3 sections:

  1. Write the primal program. (solved this section).

  2. what is the meaning of the whole/integral version of the primal problem?

  3. explain how to solve the fraction version of the primal problem efficiently?

Things i tried but im not sure of:

  1. Because there is a definition of capacity in this question i thought it might be min cut max flow or someting similar but im not sure its relevant.
  2. Because of the way edge expansion is defined ($\partial_e(S)$) and how the primal program looks like I think the constraints might enforce connectivity on the solution but im not sure about this either.
$\endgroup$
3
  • $\begingroup$ I have just a question: What is your primal problem? $\endgroup$ Commented Apr 18, 2021 at 12:44
  • 1
    $\begingroup$ @callculus , please see my answer for the primal $\endgroup$ Commented Apr 19, 2021 at 8:17
  • $\begingroup$ @AsyaOlshansky It seems fine. Thanks, although it was the job of the OP to show his/her work. $\endgroup$ Commented Apr 19, 2021 at 18:18

1 Answer 1

Reset to default
1
$\begingroup$

a) Our primal problem is the following:

Let $p_{v_1},..., p_{v_l}$ be all of paths for the graph.

And let $S_{1},..., S_{k}$ be all of our subsets ( $k=2^{m-1}$ where m is the number of edges in the graph)

Then our primal program is:

target function : min$ \sum_{j=1}^{m} c_{e_j}x_{e_j}\ $

for $1 \le i \le k $ for every $ y_{i}$ -> $\sum_{e_j \in E(S_i,V-S_i)}x_{e_j}\ \ge 1$

for $k+1 \le i \le k+l $, for every $ z_{p_{v_i}}$ -> $\sum_{e_j \in P_{v_i}}c_{e_j}x_{e_j}\ \ge d_{v_i}$

b) I think that the combinatorial is finding out a Graph G which is connected and the weight of each the path is bigger that every $d_{v_i}$ for $P_{v_i}$.

c) Here it has to do with using the elpsoid method, and choosing a seperation oracle that suits the problem. I think a seperation oracle should be Floyd Warshal but I am unable to prove this, can someone help?

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.