Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [approximation]

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

0
votes
0answers
23 views

Knapsack approximation algorithm (weights scaling)

I am trying to prove the following Knapsack approximation algorithm, the problem definition: Input: A set $S$ of $n$ objects that contains weights and values: $w_1,w_2,\ldots,w_n$ (weights) $...
3
votes
1answer
56 views

Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$

The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so ...
1
vote
1answer
83 views

Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
0
votes
1answer
30 views

Minimal edge cover of the hypergraph

We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?
0
votes
1answer
23 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 ...
0
votes
1answer
18 views

minimum cardinality maximal matching of graph

How to find minimum cardinality maximal matching? I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
2
votes
1answer
61 views

Longest-path in a graph, where the path should be 'straight'

Is there any existing work done on finding paths that are geometrically straight? I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
0
votes
1answer
12 views

Is there an FPRAS for the number of min st cuts in general graphs?

Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
2
votes
1answer
68 views

Max flow and Matching problem

Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
2
votes
0answers
21 views

Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
0
votes
0answers
16 views

Johnson-Lindenstrauss and k-means

I have a question about Johnson-Lindenstrauss and k-means. I m study a resource that explain a link between Johnson-Lindenstrauss and k-means. From what I understand, Johnson-Lindenstrauss helps us ...
1
vote
2answers
45 views

set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
42 views

Vertex Cover approximation algorithm

I have an algorithm that solves the Vertex Cover problem. The algorithm is Repeat while there is an edge: Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. ...
2
votes
1answer
27 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
14 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
21 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
109 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
27 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
22 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 ...
1
vote
1answer
34 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 ...
4
votes
0answers
86 views

Maximum-minimum-satisfiability [closed]

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
31 views

Variant of an approximation algorithm for vertex cover

Here is an approximation algorithm that finds vertex cover of a graph. ...
3
votes
1answer
97 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
19 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
25 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
20 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
30 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
36 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
53 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
68 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
79 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
33 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
219 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
87 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
20 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
10 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
31 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
54 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
92 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
43 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
24 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
58 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
360 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
42 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
73 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
45 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 ...
1
vote
0answers
26 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 ...