Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
0 votes
1 answer
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 ...
8 votes
3 answers
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
1 answer
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(...
3 votes
1 answer
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 ...
0 votes
0 answers
6 views

Load Balancing with No Overlap

Problem Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \...
2 votes
2 answers
747 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 ...
3 votes
1 answer
107 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) ...
1 vote
2 answers
89 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 $...
1 vote
0 answers
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 ...
3 votes
1 answer
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 ...
0 votes
1 answer
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
1 answer
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 ...
0 votes
1 answer
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 ...
5 votes
5 answers
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 ...
4 votes
1 answer
113 views

Approximation algorithm with runtime complexity between poly(log(1/eps)) and poly(1/eps)?

Suppose we have an approximation algorithm to some maximization problem, that returns a solution with value $(1-\epsilon)*OPT$. If the runtime of the algorithm is polynomial in the input size and $1/\...
1 vote
1 answer
40 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 ...
2 votes
1 answer
121 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 ...
2 votes
0 answers
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 ...
0 votes
1 answer
41 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{...
1 vote
1 answer
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
1 answer
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 ...
0 votes
0 answers
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
1 answer
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 ...
3 votes
0 answers
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 ...
5 votes
2 answers
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 ...
0 votes
0 answers
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 ...
2 votes
1 answer
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
0 answers
24 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
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. ...
0 votes
1 answer
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 ...
0 votes
0 answers
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 (...
0 votes
0 answers
37 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
34 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
80 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?
1 vote
0 answers
60 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
26 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
23 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
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 ...
0 votes
1 answer
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 (...
-1 votes
1 answer
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
1 answer
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
1 answer
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
1 answer
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 ...
4 votes
0 answers
75 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
77 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
292 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
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 ...
1 vote
1 answer
128 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
58 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
2 3 4 5
13