New answers tagged optimization
0
Hint:
1
This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions:
Global optimization - a branch of numerical analysis, that deals with various iterative algorithms, able to find ...
1
Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $k$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.
1
A good initial state can often be helpful. I would guess that there is a significant chance that spending extra time to find a good initial state will be useful.
All we can say in general is that "it depends". It depends on the specific problem and the shape of the fitness landscape. If the problem has few or no local minima, the search might ...
0
Let $x_1,x_2,\dots,x_n$ denote the $x$-values where the two curves intersect; you say you know how to find these. Let's add $x_0=-\infty$ and $x_{n+1}=+\infty$. Then in each interval $[x_i,x_{i+1}]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top. This is easy to ...
0
I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer.
The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.
2
You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.
Additionally, you also ...
4
For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection".
If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 ...
Top 50 recent answers are included
