# Questions tagged [approximation]

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

584 questions
Filter by
Sorted by
Tagged with
1 vote
16 views

1 vote
55 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 ...
29 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
29 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
25 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
57 views

### What is the name of this matching problem?

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 ...
22 views

435 views

### How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover

The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
55 views

### Bin Packing tight analysis lower bound?

I am having a problem understanding the following: This is the background of the lemma: To prove the lower bounds, we use the classical lower bound construction from [5, 9]. We have an input instance ...
44 views

### The solution of a nonlinear equation and eigenvalues

I have a non-zero vector $x = [x_1,\cdots,x_N]$, $0 \le x_i \ll 1$ and a symmetric matrix $M$ with eigenvalues $\Lambda_1 > \Lambda_2 \ge \dots \ge \Lambda_N$ satifying  x_i = \frac{\lambda\sum_{...
93 views

### How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded

Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
56 views

### asymptotic approximation ratio vs absolute approximation ratio?

I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different ...
82 views

### MAX-SAT approximation factor

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm MAX-3SAT: set every variable with a random value ($0$ or $1$ each ...
44 views

### Approximation Class that Decides

Suppose we have a minimization ILP. Denote its value by $OPT$. Let $PER$ be the solution to its LP relaxation. Given a real number $t$, we would like to decide whether $OPT \leq (1+t) \cdot PER$, in ...
457 views

### Traveling salesman problem on an incomplete graph

In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the ...
1 vote
15 views

### Algorithm for minimizing the number of resources simultaneously open while iterating through a series of tasks

I have a problem where I'm iterating through a series of tasks and each task requires that a specific file is loaded into memory. The files are not allowed to be unloaded until all of the tasks that ...
51 views

### State of the art implementations of minimum-cost multicommodity flow approximation algorithms

I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
### Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$ [closed]
Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \geq y_n \geq 0$ non negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ ...
### Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?
In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set \$C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...