# Tag Info

## 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