New answers tagged linear-programming
1
So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost ...
0
With the hope of providing insight into how to solve your problem, I will refer to the case of a grid $N\times N$. Let $\rho_{ij}$ denote the distance between two points $i$ and $j$, $i, j\in G$. The distances between any pair of nodes shall be stored as a parameter of your linear programming task, and can be given any values ---e.g., euclidean distance, ...
1
Let's first define some variables.
$$x_i \in \{0, 1\}$$
$$w_i \in \mathbb{Z}^+$$
Where $x_i=1\iff $ location $i$ is selected and $w_i$ equals the minimum distance from node $i$ to any selected city if $x_i=1$ and $\infty$ otherwise. We will use $D$ to represent $\infty$ and in practice $D$ can just be the diameter of the graph. We can constrain these ...
1
If I have understood your question right, this an open NP problem. For 1D problem, there is a polynomial dynamic-programming algorithm. But for 2D, there exists an approximative greedy algorithm for solving it.
Algorithm
selectedStores = {}
randCity = choose a random city
stores ∪ {A}
while 1 to k
choose the farthest city from all cities in ...
Top 50 recent answers are included
