A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [approximation]

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

415 questions
Filter by
Sorted by
Tagged with
35 views

### Calculating match % and ranking according to that

I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown ...
39 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
114 views

### Number of executions of the algorithm with probability about graphs

Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
88 views

### Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
536 views

### Derandomization of vertex cover algorithm

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$. Add to ...
57 views

### Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ ...
32 views

### Estimating number of points in 1D space

There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
56 views

### Doubt on integrality gap and LP relaxation

I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
161 views

72 views

### Approximation algorithms for indefinite quadratic form maximization with linear constraints

Consider the following program: \begin{align} \max_x ~& x^TQx \\ \mbox{s.t.} ~& Ax \geq b \end{align} where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise ...
30 views

### A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
57 views

### Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

The unweighted maximum coverage problem is defined as follows: Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$. Objective: find a subset $S' \subseteq S$ such ...
26 views

### Reductions from non decision problems

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
33 views

### Approximate algorithms for class P problems

As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
23 views

### Rearrange items in order reduce fragmentation and reduce wasted space

I have a segment with some offsets at irregular intervals There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset. Items are free ...
11 views

### What are some counter examples for Load balancing problem?

I learnt about load balancing problem under approximate algorithms. I am learning about it, and studying methods to counter part it's non -solvability under P time. I am quite out of my examples, and ...
24 views

### Randomized version of the class $APX$?

Is there a class which is to APX what BPP is to P? I'm looking for a definition that is like the following: "For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
75 views

31 views

57 views

### Clarification on NP-hardness and hardness of approximation results for set cover?

I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements. I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
112 views

### Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
87 views

### Approximation ratio of greedy algorithm for makespan

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3. ...