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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is the meaning of $\|e_{ij}\|$? $\endgroup$
    – Peter Mueller
    Commented Nov 6, 2017 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$
    – Manfred Weis
    Commented Nov 6, 2017 at 20:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Manfred Weis
    Commented Dec 3, 2017 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$
    – David Eppstein
    Commented Dec 3, 2017 at 19:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .