# Questions tagged [approximation]

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

604 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 ...
61 views

### Which combinatorial problem is reminiscent to mine?

I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an ...
3k views

### Looping and branching with Algorithmic Differentiation

Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...
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(...
409 views

### Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
6 views

1 vote
20 views

### Rectangular region biquadratic Lagrangian interpolation basis to solve dirichlet boundary Poisson equation?

after learning FEM,I try using it to solve a PDE $-\Delta u=f,u=0 on \partial\Omega$,where $\Omega$ is a square with $(0,0),(1,0),(1,1),(0,1)$being its vertex by classical finite elements.Here I use ...
360 views

### smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
104 views

### On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
1 vote
241 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 ...
276 views

### Set cover to Edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
535 views

### fast and stable x * tanh(log1pexp(x)) computation

$$f(x) = x \tanh(\log(1 + e^x))$$ The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally ...
113 views

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 ...
1 vote
79 views

### Decision version of optimization problems with polynomial-time approximation algorithms

Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class ...
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.
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 ...
39 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 ...
350 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 ...
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 ...
21 views

### Parametrized threshold for LP Approximation in Vertex Cover Problem

I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem. The linear programming ...
1 vote
24 views

1 vote
67 views

### Estimating the number of elements shared in two sets using a random sample

Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
46 views

### fault-tolerant K-median problem on an undirected graph

We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$: We are given a set of facilities $F\subseteq V$ and a set of demands (...
51 views

### if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?

if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER? the implication should be true because independent is ...
1 vote
151 views

### Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality

It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we ...
1 vote
73 views

### Hardness of the k-center problem with relaxed triangle inequality

Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
1 vote
145 views

### First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible. The problem is quite simple: Given $G = (V, E)$ an undirected graph, ...