patternMinor
Maximizing sum of ranges of vertices edges
Viewed 0 times
edgesmaximizingrangessumvertices
Problem
Consider an arbitrary undirected graph $G = (V,E)$. Suppose you have a collection of $|E|$ positive integers and each integer must be assigned to one edge. Let us denote the collection of integers assigned to vertex $v$'s edges as $w(v)$. How would one assign the $|E|$ integers to the $|E|$ edges so as to maximize:
\begin{equation}
\sum_{v \in V}{max(w(v)) - min(w(v))}
\end{equation}
In other words, how would one maximize the sum of the range of each vertice's edge assignments?
As an example, consider the graph pictured below. Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.
\begin{equation}
\sum_{v \in V}{max(w(v)) - min(w(v))}
\end{equation}
In other words, how would one maximize the sum of the range of each vertice's edge assignments?
As an example, consider the graph pictured below. Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.
Solution
I'll start by giving a negative example to @seteropere algorithm:
Let $G=(V,E)$, where $$V=\{x_1,x_2,x_3,y_1,y_2,y_3\}\ \ \ ,\ \ \ E=\{(x_i,y_i)\mid i\in [3]\}\cup\{(x_1,x_2),(x_1,x_3)\}$$
Let the weight collection be $\{3,3,2,1,1\}$.
The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x_1$, and assume that $(x_1,y_1)$ was assigned 1.
This already means that the optimal solution profit (5, see figure) is not obtainable.
That said, this problem is poly time solvable after all , greedily,
but differently.
Hint: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.
P.S.
The opposite problem, in which we aim to minimize $$\sum_{v \in V}{max(w(v)) - min(w(v))}$$
Is quite interesting by itself.
Let $G=(V,E)$, where $$V=\{x_1,x_2,x_3,y_1,y_2,y_3\}\ \ \ ,\ \ \ E=\{(x_i,y_i)\mid i\in [3]\}\cup\{(x_1,x_2),(x_1,x_3)\}$$
Let the weight collection be $\{3,3,2,1,1\}$.
The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x_1$, and assume that $(x_1,y_1)$ was assigned 1.
This already means that the optimal solution profit (5, see figure) is not obtainable.
That said, this problem is poly time solvable after all , greedily,
but differently.
Hint: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.
P.S.
The opposite problem, in which we aim to minimize $$\sum_{v \in V}{max(w(v)) - min(w(v))}$$
Is quite interesting by itself.
Context
StackExchange Computer Science Q#30841, answer score: 3
Revisions (0)
No revisions yet.