Referring to methods that produce good "approximate" solutions, particularly for np-hard, np-complete, or combinatorial optimization problems.
4
votes
1answer
72 views
What strategies one can use to keep maximum number of non attacking pieces on an $n \times n$ chess board?
What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen ...
3
votes
1answer
63 views
Expectation-Maximization and local maxima
The E-M algorithm does not guarantee convergence to global maxima. Following Applet shows this nicely: http://www.cs.cmu.edu/~alad/em/
Is it possible to generate data set, that guarantees reaching ...
3
votes
2answers
120 views
How to prove that my problem is np-hard
For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting.
The problem is that i know that this is hard to solve, but i dont know if ...
0
votes
0answers
47 views
Generate Candidate solution/ generate neighbouring solution
I am a beginner with meta-heuristic algorithms. A problem I have encountered while programming is the step: Generate a candidate solution. I have studied many papers, but none of them give me a hint ...
8
votes
2answers
335 views
Meaning of (meta)heuristic methods
For optimization, from Wikipedia:
In computer science, metaheuristic designates a computational method
that optimizes a problem by iteratively trying to improve a candidate
solution with ...
2
votes
2answers
169 views
What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?
I can see that there are multiple heuristics to acheive a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP ...
