# Tag Info

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 ...
• 39.6k
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,623
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,492
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,461
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,655

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

### Approximating a convex program

Basically $S(K, \epsilon) = K + \epsilon B$. Thus optimizing a function on $S(K, \epsilon)$ is not easier than optimization over $K$. Those approximate optimality definitions are used to measure the ...
• 153
1 vote
Accepted

### Understanding (1+ ε) approximation when objective is discrete

As requested, this answer is a combination of comments I made. I agree that if a $(1+\epsilon)$ approximate algorithm returns a feasible solution to a problem where the second best feasible solution (...
• 39.6k
1 vote

### Applications where a very high numeric accuracy is required

Curious to see if anyone knows of some better examples, but I wanted to pitch in with my experience on this in real-life scenarios. I should start by saying that in my experience this is rarely an ...
• 12.2k
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,196
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,&...
• 544

Only top scored, non community-wiki answers of a minimum length are eligible