Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
16 views

Approximation Algorithm for Bin packing Variant with Packing Overhead

I recently came up with this bin packing variant and was wondering, if someone has studied it before: Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
0 votes
0 answers
15 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 vote
1 answer
212 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 ...
3 votes
1 answer
98 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
0 votes
1 answer
27 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 ...
1 vote
2 answers
83 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
0 votes
1 answer
253 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 ...
2 votes
1 answer
119 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 ...
0 votes
1 answer
36 views

Weighted interval scheduling on K-identical machines --- approximation factor

This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor. As suggested by @D.W., I will present the problem more comprehensively. $\textbf{...
0 votes
0 answers
9 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
1 answer
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 ...
0 votes
0 answers
50 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 (...
1 vote
1 answer
62 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 ...
0 votes
0 answers
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
0 answers
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 ...
0 votes
1 answer
48 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 ...
0 votes
1 answer
78 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
3 votes
1 answer
350 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 ...
3 votes
1 answer
350 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 ...
0 votes
1 answer
98 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
0 answers
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 ...
1 vote
0 answers
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. ...
0 votes
0 answers
22 views

Maximum Subset Sum with Pairwise Constraints

(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.) Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
1 vote
2 answers
50 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 ...
0 votes
1 answer
45 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 (...
-1 votes
1 answer
39 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
1 answer
132 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
1 answer
49 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
1 answer
95 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 ...
4 votes
0 answers
74 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
1 answer
71 views

Can we show that #3CNF is in FPTAS

If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
3 votes
1 answer
137 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$. ...
1 vote
0 answers
42 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 ...
1 vote
1 answer
73 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 ...
0 votes
0 answers
41 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 ...
2 votes
0 answers
84 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 ...
1 vote
0 answers
31 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 ...
0 votes
3 answers
183 views

Numerical Approximation in Java

I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is: $$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{...
1 vote
1 answer
184 views

Job scheduling approximation

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....
0 votes
0 answers
110 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 ...
0 votes
3 answers
184 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 ...
7 votes
5 answers
2k views

What is the fastest algorithm to approximate an irrational number with specified precision?

Problem Background: Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
1 vote
1 answer
97 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: ...
2 votes
1 answer
384 views

An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
2 votes
0 answers
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 ...
0 votes
0 answers
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?
0 votes
1 answer
59 views

Geometric Set Cover in one dimension

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
1 vote
1 answer
65 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. ...
1 vote
1 answer
162 views

Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size

I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$. If we pick ...
0 votes
1 answer
105 views

To write an IP and relax it to LP for finding a multi-set in a graph

I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given: A digraph ...

1
2 3 4 5
12