Skip to main content
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 ...
prubin's user avatar
  • 39.6k
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 ...
fontanf's user avatar
  • 2,623
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 ...
Discrete lizard's user avatar
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 ...
Joris Kinable's user avatar
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 ...
user3680510's user avatar
  • 3,655
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 ...
Tim Varelmann's user avatar
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 ...
Red shoes's user avatar
  • 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 (...
prubin's user avatar
  • 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 ...
Nikos Kazazakis's user avatar
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.
Dan's user avatar
  • 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\...
xd y's user avatar
  • 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,&...
Max's user avatar
  • 544

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