1
$\begingroup$

Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges.

Consider a $T \subset V$, and $u \notin V$.

I'm trying to develop algorithm for following optimization problem:

Adding minimal new edges (that have fixed costs that is greater than any already existed edge), which decrease the cost of

$ \min (||E^{+}||+\sum_{ \forall w \in T} d(u,w))$, where we define $d$ to be the cost of the shortest path between $u$ and $w$, and $||E^{+}||$ is the cost of adding $|E^{+}|$-new edges.

The simple algorithm (see explanation in [1]) would have the following complexity (just using a Bruteforce).

$ (\sum_{i= 1}^{|T|} {n \choose |i|}) \cdot |T| \cdot SPT$ where, we denote SPT as the complexity of the best shortest path algorithm to to a single path $(u,w)$.

But, I'm sure there exist better heuristics approaches.

I appreciate any existing reference if this problem is already solved, or similar problems if it is open question.

[1]- Explanation:

Add 1 edge to any of the graph and compute the formula , then add 2 arbitrary edges and compute where is the minimum. Keep on going till adding |T| edges, i.e connect directly u to any node in T. Then, choose the construction that has minimal cost

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Your question is written very cleanly. Can you clarify that the graph must always be a simple graph? That is, is multi-graph not allowed? Do you mean each new edge has same cost or not? $\endgroup$ – Apass.Jack Oct 19 '18 at 1:01
  • $\begingroup$ $\sum_{ \forall w \in T}$ should be $\sum_{w \in T}$. ${n \choose |i|}$ should be ${n \choose i}$. $\endgroup$ – Apass.Jack Oct 19 '18 at 1:01
  • $\begingroup$ Thanks! For your questions: 1) The graph might not be simple (i.e. might has cycles) 2) for the problem simplicity, multigraph is not allowed (i.e. there are no parallel edges). 3) each new edge has same cost, which is bigger than any weight on existing edge (i.e. existing edges might have different edges, but when we add edge we pay same cost). $\endgroup$ – user1387682 Oct 19 '18 at 3:35
  • $\begingroup$ In that summation, I tried to express the following algorithm: Add 1 edge to any of the graph and compute the formula , then add 2 arbitrary edges and compute where is the minimum. Keep on going till adding $|T|$ edges, i.e connect directly $u$ to any node in $T$. Then, choose the construction that has minimal cost. $\endgroup$ – user1387682 Oct 19 '18 at 3:41
  • $\begingroup$ If this problem comes from an online programming contest or a coding camp, please add a URL. If it comes from a book or a paper, a reference. If this problem comes from your real life, some background. Besides paying proper attribution to the original source, all those information motivate and help people answer the question faster and better. Please add those information in the question since people and search engine are not expected to look at comments. $\endgroup$ – Apass.Jack Oct 19 '18 at 13:41

Your Answer

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

Browse other questions tagged or ask your own question.