Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
358 questions
2
votes
1answer
22 views
what is a shearlet/shearlet transform and how can i use it?
from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles ...
1
vote
1answer
12 views
Approximation factor shorthand clarification
I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
1
vote
0answers
20 views
Determining a value in an algorithm on its first run
I was given the following algorithm as a solution to one of my problems.
However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
1
vote
0answers
95 views
Proving there is no polynomial algorithm for independent set
I need some guidance in an assignment I'm doing.
I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
1
vote
0answers
23 views
Sort-of interval scheduling
The Problem
I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize...
the number of pairwise ...
1
vote
1answer
17 views
Defining Gap Problems
I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across ...
0
votes
0answers
75 views
Squared euclidean distance high probability bound
I wish show squared Euclidean distance between $x$ and $y$ (they are 2 point uniformly at random in $[-1,1]^d$ ) is at least $(1-\epsilon)cd $ with probability $e^{\Theta \epsilon^2d}$ with $c<1$.
...
1
vote
1answer
32 views
Amplification for Randomized Algorithms
I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.
Amplification for randomized algorithms:
Given a randomized algorithm with time ...
3
votes
0answers
40 views
+50
Maximum-minimum-satisfiability
In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
1
vote
1answer
29 views
Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.
...
0
votes
0answers
35 views
Family of graph with Approximation ratio = 2
My question today is about the approximation algorithms. Well, for Approx-Vertex-Cover problems , we know we can get ratio of 2 just by picking an edge and taking 2 endpoints of the same and ...
3
votes
1answer
60 views
Christofides algorithm (by hand)
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[![enter image description here][1]][1]
...
0
votes
0answers
17 views
Converting an approximate algorithm for the minimization to the maximization form
I have a $\rho$-approximate algorithm for a minimization algorithm, where the objective is to minimize $O$ ($\rho \geq 1$ is some constant), such that the algorithm's solution is always within $\rho$ ...
1
vote
1answer
22 views
About a pre-processing step for primal-dual weighted set cover problem
I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.
They present a dual fitting based algorithm ...
1
vote
1answer
19 views
The notion of PAC in approximation algorithms
In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is ...
1
vote
1answer
27 views
Knapsack-like problem oriented on contiguous selection
Problem inputs is an ordered array $A = [a_1, a_2, \ldots, a_n]$ with $\text{weight}(a_i) = w_i$.
We define a $subgroup$ of $A$, denoted by $B$, whose elements' indices are continuous in integer. For ...
2
votes
0answers
33 views
Different properties of Heavy-Hitters and Count-Min Sketch algorithms?
I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
1
vote
0answers
41 views
$k$ -center with outliers - but the points are on a line
The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it.
However, what if we assume that the input point are on a line, rather than in an ...
1
vote
1answer
33 views
Is deep learning appropriate to approximate dynamic programming problems?
I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000). I won't get into the details of the problem since it's a bit ...
-1
votes
1answer
54 views
A question about a variant of a knapsack problem
I have the following problem:
Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
5
votes
1answer
69 views
Hardness of approximating Minimum Cardinality Exact Cover
The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.
Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for ...
1
vote
0answers
32 views
Are there matching upper bounds?
When reading about approximation algorithms, I often find the terms "matching lower bounds". As I understand, these means to provide examples where the approximation algorithm matches the proved ...
3
votes
1answer
182 views
Big-O / $\tilde{O}$ -notation with multiple variables when function is decreasing in one of its arguments
Say we have an algorithm that
takes an input a triple
($X$, $A$, $\epsilon$),
where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are ...
1
vote
1answer
63 views
When to terminate search for path in an infinite grid
I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in ...
0
votes
0answers
19 views
What would be a generic strategy to proof $\alpha$-approximation algorithms?
I am studying combinatorial optimization (mainly problems that can be represented on graphs and 0-1 IP optimization) and have come across many $\alpha$-approximation algorithms for certain problems. ...
2
votes
1answer
21 views
Ensure groups of four 3-tuples have 9 unique numbers
Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.
Suppose you have 200 bins. Each bin would be very happy to ...
0
votes
0answers
9 views
Why does economising the power series give me more error?
Suppose I want to economise $\sin x$ with the following taylor series:
$$P_{2n-1}(x) = \sum^n_{i=1}(-1)^{i-1}\frac{x^{2i-1}}{(2i-1)!}$$
for the interval $[-1, 1]$ for $P_5(x)$.
For $P_5(x)$, I have ...
0
votes
0answers
28 views
How Does Aproximate Reinforcement Learning Reduce State Space?
I was following reinforcement learning lecture from "CS188 Artificial Intelligence, Fall 2013". Here is the slide:
In the video, the lecturer says with approximate reinforcement learning we store ...
2
votes
0answers
47 views
An approximation for the sum of k largest elements of n-sorted arrays?
Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements.
All elements are between 0 and 1, and the the sum of all elements in array $i$...
4
votes
1answer
90 views
Equivalent Colorings of Graphs
Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors.
In other words, they are the "same" coloring.
I'm interested in finding proper non-...
0
votes
1answer
41 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 ...
0
votes
1answer
20 views
Approximation factor for graph problems
I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.
For example, if a graph G actually has a maximum clique with 13 ...
1
vote
0answers
23 views
K-approximation algorithms [duplicate]
I am attempting to understand exactly how the terminology for k-approximation algorithms work, from when k is known and determining what k is.
If we assume that a vertex cover in a graph G is of size ...
0
votes
1answer
56 views
Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems ...
1
vote
1answer
356 views
What does Arora mean by 'computational history'?
In Arora's paper, he wrote,
Papadimitriou and Yannakakis also noted that the classical style of reduction (Cook-Levin-Karp [41, 99, 85]) relies on representing a computational history by a ...
1
vote
0answers
38 views
Spanning tree with equally separated edge weights
I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
1
vote
0answers
72 views
subgraph that verify certain condition
Given an undirected graph $G=(V,E,p,c)$ and a positive integer $k$, $p: V \longrightarrow R^+$ which associates a positive weights $p(v_i)$ to every node $v_i \in V$, and $c: E \longrightarrow R^+$...
1
vote
0answers
43 views
How to find a Graph Embedding given a metric space? [closed]
I am interested to learn more about Topological graph theory and Graph Embedding.
Assume I have a metric space, $d \colon M \times M \to \mathbb{R}$ and a graph, $G=(V,E)$.
What is a rigorous way ...
0
votes
0answers
37 views
Competitiveness of bin packing with allocation constraint
I am working on a variant of the variable sized vector bin packing problem that is subject to an allocation constraint, where items can be put in a few particular bins only, not any bins. This item-...
1
vote
0answers
25 views
Hardness of approximation for online algorithms
Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds ...
0
votes
0answers
35 views
How does one find the maximum of $\{ \eta \in \mathbb R : |h(\eta)| \leq \epsilon \}$ using line search?
Assume I have a function that is computable in polynomial time $h(\eta)$ where $h: \mathbb R \to \mathbb R$. I am interested in computing the following supremum (approximately and in polynomial time ...
0
votes
0answers
14 views
difference between integrality gap and approximation ratio [duplicate]
What is the difference between integrality gap and approximation ratio? Any example to elaborate the difference?
3
votes
0answers
61 views
Is there an optimization problem on planar graphs which is APX-hard ?
I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
2
votes
1answer
71 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-...
1
vote
1answer
56 views
Knapsack with non-overlapping rectangles
Given a large rectangle and a set $S$ of small rectangles each with a value $v_i$. My problem is to find a collection of rectangles $T\subseteq S$ to put in the large rectangle so as to maximize the ...
1
vote
0answers
41 views
Finding minimum number of bicliques that cover nodes on one side of a bipartite graph
Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', ...
2
votes
1answer
38 views
How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?
Theorem 11.4 For any constant $\delta > 0$, every problem in NP has probabilistically checkable proofs of length poly($n$), where the verifier flips $O(\log n)$ coins and looks at three bits of the ...
2
votes
1answer
61 views
Finding bicliques in a bipartite graph of minimum size
Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', ...
0
votes
3answers
97 views
How approximate sine using Taylor series
I need to approximate the sine function without internal libraries. I used Taylor series in 0 to solve this, but my program works for some values, but for others awful results.
The program gets x ...
1
vote
0answers
68 views
Why gap preserving reduction is weaker than L-reduction?
In Vizirani's textbook says in page 332,
Gap preserving reductions are weaker than their L-reductions [...] one of the motivations for the PCP theorem was that establishing an inapproximability ...
