Share Your Experience: Take the 2024 Developer Survey

Questions tagged [approximation]

Questions about algorithms that solve problems up to some bounded error.

595 questions
Filter by
Sorted by
Tagged with
21 views

Integrality gap of Maximum Coverage LP

Consider Maximum-Coverage problem, which means there are set $A$ and $n$ subsets of $A$, we can choose $k$ subsets to cover some elements, and Maximum-Coverage is the assignment that cover most ...
1 vote
33 views

What kind of problem am I trying to solve?

I have 500 locations that have multiple skus with varying quantities and I have 6000 orders requesting multiple skus with varying quantities. I have to minimize the total number of locations I visit(...
• 13
7 views

• 6,030
38 views

Is there a 3-approximation algorithm for the TSP problem?

I know the double tree algorithm and Christofides algorithm with 1.5 approximation ratio. We got this question from the teacher.
• 83
1 vote
45 views

Can PTAS be used to optimally solve Knapsack?

Suppose you have a Knapsack (optimisation) problem with integer values and weights, and you know the optimal value $OPT$. Can you compute an optimal solution in polynomial time by using a PTAS or ...
• 807
40 views

Approximation of the Normal Set Basis Problem

Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$. The input of ...
• 2,931
352 views

How to find an example for a case in the metric k-center problem

Given $n$ points in a 2d metric space, the $k$-center problem asks us to find a subset of size $k$ of the points which we will call centers. The task is to pick these centers to minimize the maximum ...
• 996
31 views

The approximation ratio of approximation algorithm

I am studying the approximation algorithm. I have a question as follows. For an approximation algorithm for maximization problem, if I have $sol \ge \alpha opt - c$, where $c$ is a positive constant ...
1 vote
24 views

• 11
1 vote
62 views

Weighted interval scheduling with m-machines ---greedy solution with approximation factor

Weighted interval scheduling with m-machines ('Weighted interval scheduling with m-machines') I encountered the problem of weighted interval scheduling on m identical machines (as discussed in the ...
• 11
37 views

Calculating approximation factor of a TSP algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
1 vote
35 views

Scheduling jobs with the same release time and different due dates on a single machine

Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
1 vote
26 views

What is the name of this extension of the maximum independent set problem?

Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
1 vote
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...