# Tag Info

## Hot answers tagged approximation-algorithms

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
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
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
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
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

### 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 ...
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 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