使有向圖中的最小邊+節點值最大化

我有一個有向圖。每條邊都有固有的「重量」w_ij，這是固定的。每個節點的值爲v_i，除了「根節點」（沒有傳入邊）和「葉節點」（沒有出現邊）的值固定外，其他值都可以配置。使有向圖中的最小邊+節點值最大化

每個邊緣的「由節點調整」邊緣值由下式給出： s_ij = w_ij + v_j - v_i也就是說，我們通過其相鄰節點的值的差值來調整邊緣的值。當然，更改節點的值將影響s_ij的值。

我對min{s_ij}的值感興趣，並希望找到節點的最佳值分配，以便使此「瓶頸」值最大化。

任何想法如何做到這一點？

注意：從根到葉的循環和「固定路徑」爲最小值提供了上界（例如在一個循環中，節點差的總和始終爲0，所以最好的結果是邊緣內在權重的平均值）。但是因爲循環和「固定路徑」可能重疊，所以最小上限是否可以達到目前尚不清楚。解決方案可能首先涉及找到這樣的路徑/週期。

評論，想法，見解都是受歡迎的。

來源

2013-06-23 amit

聽起來像一個經典的流量問題。看着埃德蒙茲卡普普流。我會詳細闡述一下，但我在移動。 http://en.m.wikipedia.org/wiki/Flow_network –

謝謝。我最初想到流程問題，但想不到直觀的減少 - 我會看看你的建議。只是爲了給出一些上下文，問題出現在調度/同步問題中，並且s_ij值是鬆弛時間或類似的東西 – amit

我能想到的馬上兩種不同的方法：

首先，你可以對答案二進制搜索。檢查您可以獲得給定的最小邊權重與最短路徑問題密切相關---您對節點權重的差異有一系列約束，每個約束的形式爲w _i - w _j> = l _ij某些w是固定的。其次，你可以做subgradient optimisation。您想要最大化邊權重的最小值。在這裏制定一個亞梯度是很容易的。

這個問題可能有很多有用的結構，我不在這裏開發。你可能會嘗試寫下一個線性編程的放鬆和玩一些。這樣做---更深入地分析問題---幾乎肯定會導致比上述兩種方法更快的算法。

來源

2013-06-23 17:02:27 tmyklebu

實際上，我不會對一個好的次梯度下降方法下注。 –

@DavidEisenstat：我也不會。感覺就像那種你可以做一些快速組合的東西。 – tmyklebu

如果我理解正確，可以將該問題表述爲該線性程序。調整輸入，使v_i = 0爲每個頂點i即源或接收器。

maximize z 

subject to 
for every ij, 
    z + v_i - v_j <= w_ij (i.e., z <= w_ij + v_j - v_i = s_ij) 

variables 
z unbounded 
for every vertex i not a source or sink, 
    v_i unbounded

這是雙程序。

minimize sum_ij of w_ij y_ij 

subject to 
sum_ij y_ij >= 1 
for every vertex i not a source or sink, 
    sum_j y_ij - sum_j y_ji = 0 

variables 
for every ij, 
    y_ij >= 0

如果我們沒有從保守約束中排除源和匯，那麼這就是最小平均成本週期的線性規劃。就目前情況而言，我們仍然可以使用流量分解技術來表明存在一個最佳的源 - 匯路徑或一個循環，並且我相信對於找到最小平均成本週期的簡單算法稍作修改是適用於此。

一旦你有最佳值z*，你可以找到潛力v_i通過運行貝爾曼福特與權重w_ij - z*。我很抱歉沒有提供更多的細節，但我有這種嘮叨的感覺，我正在做你的功課。

來源

2013-06-23 17:09:04

請放心，您不是在做我的功課，我很感謝您的回答 - 減少線性規劃問題是我沒有想過的。我很高興我將它描述爲一個「圖論」問題，我朝着這個方向看。正如我在另一條評論中所寫的那樣，問題出現在同步/調度問題中，並且我制定了一個在現實世界中試圖解決的問題的簡化版本。 – amit

使有向圖中的最小邊+節點值最大化

回答

相關問題