Re: Can this be solved in polynomial time?

Thanks for the swift reply.
I see your reasoning. It's what I feared.
I would however be satisfied with an algorithm that can find a near-
optimal solution with high probability. The trivial greedy algorithm
doesn't seem good enough.
One possibility may be to use some randomized algorithm and run it
enough times to get a high probability of a near-optimal solution.
Any ideas?

.

Relevant Pages

  • Re: Measuring the effectiveness of a GA implementation?
    ... GA - or of any optimisation algorithm, ... comparison with an optimal solution is ... mean fitness) plus, preferably, some measure of the ... about evaluating effectiveness of optimisation algorithms (I'm loath to ...
    (comp.ai.genetic)
  • Re: Needleman-Wunsch - producing more than the optimal solution -- please help
    ... What I want is the optimal solution, second optimal solution, third ... an issue I see is that it's not clear to me that the algorithm actually compares solutions to find the "optimal" one so much as it detects the best alignment of two inputs based on a pre-computed weighting matrix. ... But the moment you allow for the choice of something other than the maximal choice, you have to deal with every permutation possible, and evaluate those permutations in some way. ... Not only would you, after redoing the choice, have to recompute the rest of the "F" matrix that depended on that choice, there's no guarantee that when you're done, the score in the lower-right corner that results from that replacement would indeed be the next-lowest score possible in the matrix. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Shortish paths
    ... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: C to Forth converter?
    ... how to find the minimum number of instructions for solving a stack juggling ... But is this the shortest solution? ... algorithm to converge towards. ... optimal solution because the only way to find that it is optimal is to ...
    (comp.lang.forth)
  • Re: Shortish paths
    ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)