New answers tagged optimization
0
Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once. At that point, you are just looking for the longest path.
Your generalization, allowing partial conversions, non-constant functions,...
0
It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. ...
1
As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).
0
Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A[i])$ represents a point in 2D-space. Also we can think that assigning $A[j]=0$ is the same as removing the point $(j, A[j])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A[i])$.
Now the set of ...
0
Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.
Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.
The vertex set in your problem will coincide with $V$. Choose the concave function $c_e(x)$ that describes the cost of ...
Top 50 recent answers are included
