# Questions tagged [approximation]

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

599 questions
Filter by
Sorted by
Tagged with
25 views

### Adding edges to enlarge vertex cover

Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
• 388
372 views

### Applicability of approximation algorithms vs meta-heuristics in practice

How useful are approximation algorithms over say, metaheuristics or even problem-specific heuristics in practice? Let's say a certain NP-hard minimization problem (take the travelling salesman problem ...
• 388
55 views

• 127
1 vote
21 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 ...
1 vote
41 views

### Can you identify this assignment problem and efficient solutions or estimates?

Problem Statement My wife's business runs a summer camp for 68 students. The students are divided into cabins: 27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins; 41 ...
50 views

### Approximate the parity function in L1-norm

Consider the parity function $MOD_2(x) = x_1 \oplus \cdots \oplus x_n$ for $x \in \mathbb{F}_2^n$. I am concerned about the degree bounds for a real polynomial $f$ which approximates $MOD_2$ well in ...
• 21
114 views

24 views

### better ways to integer interpolation?

I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation. ...
• 1
35 views

### Optimal randomized algorithm for set cover

This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem ...
22 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 ...
52 views

### Understanding the "Structure Theorem" for the Euclidean Traveling Salesman PTAS

I am trying to understand the "Structure Theorem" in Arora's TSP slides. In particular, I do not understand the image on slide 13-3 (page 68 of the PDF). The high level idea is to show that (...
• 232
47 views

1 vote
78 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 ...
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
81 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
162 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 ...
122 views

### Budgeted Independent Vertex Cover

Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
• 131
76 views

### Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph

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

### How to prove this simple randomized algorithm is 2-approximate for MAS?

The Maximum Acyclic Subgraph (MAS) problem is: Given a directed graph $G = (V, E)$, find the largest subset of edges which are acyclic. In this paper the authors state the following algorithm: A ...
• 173
1 vote
56 views

### Can there be a 1.1 approximation algorithm for the load balancing problem?

I know this is a very specific question, but: Let's assume that someone designed a 1.1 approximation algorithm for the load balancing problem involving exactly 2 machines. After running the algorithm ...
308 views

### Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The following problem statement is given: Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
60 views

### Hardness of the bin packing problem

I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that $$1 > a_1 \geq a_2 \geq \dots \geq a_n > 0$$ The ...
1 vote
84 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 ...
• 6,070
1 vote
152 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
43 views

### How to show that my problem cannot be approximated within a certain factor unless P=NP?

Before I introduce my problem I need to define a couple of things. Suppose we have two sets $S_1=\{1,2,3\}$ and $S_2=\{2,3,4\}$. A compression tree for $S_1$ and $S_2$ is ...
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 ...
90 views

### Finding a maximum induced DAG in a digraph

I have a digraph D on n vertices formed in the following manner: I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
• 71
1 vote
133 views

### Does there exist an FPTAS for bin packing problem?

We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
313 views

### Details of sqrt.c library source code

Have seen library code for finding square-root, using the Newton Raphson method. It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity ...
• 187
1 vote
109 views

### Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?

The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation: Start with empty set $S$ As long as not all vertices are covered: ...
45 views

### Designing Shortest Route

Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
• 63
17 views

### Can a PTAS be called one if it is parameterized by one of the problem inputs (in addition to ε)?

I.e. is it right to say "a PTAS parameterized by sth"? Is it unusual, and is it correct?
49 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 (...
• 15
1 vote
72 views

### Bin packing with more than one parameter

Usually, in bin-packing, we have objects of sizes $a_1,...a_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms. ...
• 63