1
$\begingroup$

Are there algorithms for finding $\omega_1\dots,\omega_n$, so that

$\omega_i+\omega_j\le \|e_{ij}\|\ \forall i,j\quad\wedge\quad\sum{\omega_i}=max$

that are not based on linear programing, e.g. graph theoretic algorithms?


Remark:
the number of constraints in the $LP$ formulation can be reduced on basis of the following observation:
let $\mu_i$ be the mimimum of the weights of edges, that are adjacent to vertex $v_i$ (in the graph interpretation of the problem); then $\omega_i+\omega_j \le \mu_i+\mu_j$ (because of the non-negativity constraints) and edges, for which $\|e_{ij}\|\ge\mu_i+\mu_j$ trivially satisfy $\|e_{ij}\|\le\omega_i+\omega_j$ which implies, that the respective constraint need not be included in the $LP$ formulation.
The impact of that reduction can be increased in some cases by subtracting from all edge weights the weight of the shortest edge and adding it to the $\omega_i'$ constituting to the solution of the modified problem.

$\endgroup$
2
  • $\begingroup$ What is the meaning of $\|e_{ij}\|$? $\endgroup$ Nov 6 '17 at 19:01
  • $\begingroup$ @PeterMueller I used it as a shorthand for the weight of edge $e_{ik}$; if that is confusing, I will edit my question accordingly. Thanks for the feedback. $\endgroup$ Nov 6 '17 at 20:32
1
$\begingroup$

See my recent paper "Maximizing the sum of radii of disjoint balls or disks", J. Computational Geometry 8 (1): 316–339, 2017, http://doi.org/10.20382/jocg.v8i1a12, on problems like this. It is the dual of the LP relaxation of a weighted matching problem, and (even though the relaxation allows fractional solutions instead of just 0-1 solutions) it can be solved by graph matching based algorithms.

$\endgroup$
2
  • $\begingroup$ The maximum vertex-weight sum need not have 0-1 solutions either, albeit simple greedy heuristics can easily be envisaged that amount to a 0-1 selection of the $\mu_i$. Having said that, I don't see, how the maximum weight sum problem can be reformulated to amount to the maximal sum of radii problem, because there one has to determine an optimal subset of the balls "only" and does not additionally have to find weights for balls. If however a minimum volume were prescribed for each ball, allowing to deflate individual balls, then that problem would IMHO be equivalent. $\endgroup$ Dec 3 '17 at 15:02
  • $\begingroup$ There are no subsets in the sum of radii problem: it is exactly that one has to find a radius $\omega_i$ for each point $v_i$, maximizing $\sum \omega_i$, and constrained by two points with distance $d_{ij}$ have radiii that keep their balls far enough apart: $\omega_i+\omega_j\le d_{ij}$. So it seems to be exactly what you write. $\endgroup$ Dec 3 '17 at 19:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.