Given a DAG $G=(V,E)$, with non-negative weights $ w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that:

  1. $\forall u,v\in V$ and $\forall p_1\neq p_2 $ paths from $u$ to $v$, the weights ratio of $p_1$ and $p_1$ is at most 2.
  2. After modifications, the weights are non-negative

The cost of modifying the weight of an edge $e$ is $ c_e \, \forall e\in E$. The goal is to minimize the total cost of modification, namely $\sum_{e\in E}c_e|w_e-w'_e|$, where $w'_e$ is the weight of $w_e$ after the modification.

When formalizing this problem as a LP, there's an exponential number of constraints (as the number of paths between all the vertices is exponential). I thought maybe there's a property of the DAG that can be helpful, either to avoid the exponential number of constraints, or to establish an oracle for the LP.

Any ideas?

  • $\begingroup$ Thank you @D.W. I updated the question, hope it is clearer now. $\endgroup$ – Mega Dec 18 '16 at 9:00
  • $\begingroup$ Much clearer now! Thank you. Would you mind sharing where you encountered this problem? Did you run across it in practice? Are you working on an exercise to help understand linear programming? Is there some context/motivation? That might help us give you a better answer. $\endgroup$ – D.W. Dec 18 '16 at 17:53
  • $\begingroup$ This question is a part of an exercise in optimization and approximation course, that we were given after learning about LP and the ellipsoid algorithm. Actually, I believe I managed to find a solution during the last two days. I'll upload it once I write it down. $\endgroup$ – Mega Dec 19 '16 at 11:34

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.