7
votes
Accepted
Is Dantzig-Wolfe decomposition an example of a divide and conquer algorithm?
I've never seen D-W referred to as "divide and conquer." While I'm not sure there is a definitive answer one way or the other (meaning I don't know that anyone can say with authority that it ...
- 37.9k
4
votes
Accepted
Optimize selection of metal sheets to keep in stock
If I understand well your problem, a good way to tackle it is to model it as an integer linear program and solve it with a mixed-integer linear programming solver, such as CBC, SCIP or Highs for the ...
- 2,495
4
votes
Accepted
Christofides algorithm, transform from Eulerian tour to Hamiltonian cycle
The weight sum of all edges in the Eulerian tour created in Christofides algorithm is already at most $3/2$ times the weight sum of a TSP tour. While there are multiple ways of shortcutting the ...
- 1,482
4
votes
Accepted
Which constructive heuristics exist for the time-dependent TSP?
You could use any existing constructive heuristic to compute a TDTSP solution.
Let $T_{ij}(t)$ be the travel time on arc $(i,j)$ when departing location $i$ at time $t$. A common premises is that it ...
- 3,396
3
votes
Accepted
If a problem is inapproximable for $(2-\epsilon)$, can we conclude there exists no PTAS for it?
You can conclude There exists no PTAS for Problem P1 if $P \neq NP$, but you can NOT conclude P1 is APX-hard. Precisely:
If someone proofs $P = NP$ you get a trivial PTAS;
Assumung $P \neq NP$, it ...
- 3,635
3
votes
multi stage stochastic programming algorithm
If your question is “Are nested Benders decomposition or progressive hedging more efficient than solving a very large-scale monolithic formulation (sometimes called ‘deterministic equivalent’) with ...
- 136
1
vote
Steiner tree sub-optimal algorithm always finds the optimal solution. Why?
The problem is NP-hard in general. I suspect that your problems are rather small or have few terminals and are therefore easy to solve, even for an approximation algorithm.
- 21
1
vote
Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?
There is an upper bound about some complexity of some kind interior-point method given by cvxbook in P589 Eq. (11.26), (11.27), where the tolerance appears in a constant
\begin{equation}
c = \log_2\...
- 1,046
1
vote
Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?
(I will take a shot at answering my own question.)
I believe the answer to the question posed in the title is, basically,
Yes.
When people say that convex programs are "polynomially solvable,&...
- 534
Only top scored, non community-wiki answers of a minimum length are eligible