Questions tagged [approximation-algorithms]
For questions asking about approximation algorithms. Also includes approximation schemes, PTAS and FPTAS.
23 questions
3
votes
0
answers
60
views
Efficient Approximate Algorithms for Large-Scale Multiple Traveling Salesperson Problems
I need to solve several kinds of multiple Traveling Salesperson Problems; single-depot mTSP, multiple-depot mTSP and constrained multiple-depot mTSP.
The number of nodes range from 500 to 2000.
The ...
- 31
0
votes
2
answers
139
views
Distribution Evaluation for SAA
I understand that Sample Average Approximation (SAA) in optimization is considered as an approximation model using the law of large numbers (such as in this link). Therefore the approximation of the ...
- 35
2
votes
1
answer
218
views
Solve a combinatorial problem under nested cardinality constraints
I am trying to solve the following optimization problem
\begin{align}
\underset{S_t \in \mathbb{S}}{\min} ~ \sum\limits_{S \subset S_t:|S| = M} f(S)
\end{align}
where $\mathbb{S} := \{S \subset \...
- 43
2
votes
1
answer
81
views
How to correctly interpret the $\ln(n)$ approximation ratio of the set cover problem under its integer formulation context?
The wikipedia article of the set cover problem stated the following point regarding the inapproximability of the greedy method "When $n$ refers to the size of the universe.... it cannot be ...
1
vote
1
answer
57
views
Traverse discrete approximations to a continuous system
I have a system of equations looking like
$$
\frac{2.8 R_{6}}{R_{4} + R_{6}} = \frac{5.2}{\left(\frac{1}{R_{2}} + \frac{1}{R_{1}}\right) \left(R_{7} + \frac{1}{\frac{1}{R_{2}} + \frac{1}{R_{1}}}\right)...
- 592
2
votes
0
answers
73
views
Does there exist a constant factor approximate solution for capacitated vehicle routing problem?
I know that there is a 1.5 approximate solution for metric traveling salesman problem (TSP), e.g., Christofedes algorithm guarantees this. Is there an algorithm that guarantees a constant factor ...
- 111
1
vote
0
answers
140
views
Solving convex separable programming problem using interior point method?
In my engineering application, all decision variables are non-negative and everything is convex separable. In addition to that, the only function that I am trying to approximate with grid point are $f(...
2
votes
1
answer
161
views
Approximating a convex program
As I understand it, "approximating" a convex program usually refers to finding a solution that is approximately-feasible approximately-optimal.
For example, in the book "Geometric ...
- 73
1
vote
1
answer
127
views
Understanding (1+ ε) approximation when objective is discrete
Some problems in operations research have (1+ε) approximation algorithms which run in polynomial time. So we have an algorihm that produces a solution which is whose objective is within that factor (1+...
- 4,307
4
votes
1
answer
179
views
Applications where a very high numeric accuracy is required
In numeric algorithms, an important parameter is the accuracy. Usually, the run-time of such algorithms, when they are required to return an $\epsilon$-approximate solution, is a function of $1/\...
- 1,049
5
votes
1
answer
298
views
Optimize selection of metal sheets to keep in stock
I already asked this on stack overflow but just found this forum instead and figured it was more suited here. If this isn't allowed please feel free to tell me and I'll delete the post.
I am doing ...
- 53
2
votes
1
answer
319
views
Is Dantzig-Wolfe decomposition an example of a divide and conquer algorithm?
Typical Divide and Conquer algorithm solves a problem using following three steps:
Divide: This involves dividing the problem into smaller sub-problems.
Conquer: Solve sub-problems by calling ...
- 153
3
votes
1
answer
100
views
Steiner tree sub-optimal algorithm always finds the optimal solution. Why?
I am using the algorithm implemented by the library networkx to solve a Steiner minimal tree problem.
They claim their algorithm to give an approximated solution.
...
- 571
2
votes
1
answer
245
views
multi stage stochastic programming algorithm
I have a multi-stage stochastic programming model. I have 3 groups of variables: the first group takes values at the beginning of the planning horizon before the first realization and does not change ...
- 21
10
votes
2
answers
578
views
Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?
Motivating example
This question concerns continuous convex minimization. However, the motivating example is the classic binary knapsack problem
$$\text{maximize}\quad v^T x \qquad \text{subject to}\...
- 614