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

learn more… | top users | synonyms (1)

0
votes
0answers
13 views

Optimizing the output parameters for a given input

Problem statement: I'm trying to solve a problem statement using C# as programming language. In the problem system for an input (double/decimal) say Hi, the output generated is a form of dataset ...
1
vote
1answer
73 views

Prize collecting Steiner tree on graph without weights on edges

I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is ...
1
vote
1answer
33 views

About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have, $SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$ where we mean, $SDP(G)$ = The maximum value that the SDP finds of the objective ...
4
votes
0answers
76 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
1
vote
1answer
19 views

Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if ...
3
votes
1answer
21 views

Approximation for vector bin packing

I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing. To clarify, inputs to the bin packing problem ...
4
votes
1answer
43 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
1
vote
0answers
13 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil ...
2
votes
1answer
27 views

Methods for proving upper bound on a-approximiation algorithms? [closed]

I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance. For example, there's a simple randomized algorithm for the ...
1
vote
0answers
22 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $Η$ is the current graph, until there are no more cycles left.What ...
4
votes
1answer
130 views
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
1
vote
1answer
53 views

How Splitting Summation method works

I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and ...
0
votes
0answers
23 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...
6
votes
1answer
165 views

Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant ...
3
votes
1answer
39 views

What is the sqrt(n)-approximation algorithm for set packing problem

The set packing problem is : Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of ...
2
votes
2answers
39 views

Hardness of approximation: what decision problem is hard exactly?

Just a question for personal comprehension. Consider the following statement: It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$. ...
0
votes
1answer
27 views

How does Hassin's algorithm for the Restricted Shortest Path work?

I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds ...
3
votes
1answer
67 views

Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ ...
2
votes
1answer
63 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is ...
2
votes
1answer
83 views

Approximate Subset Sum with negative numbers

I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states: If all numbers are ...
5
votes
2answers
76 views

Why does this graph show the tightness of MST heuristic's 2-approximation bound?

This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a ...
1
vote
1answer
17 views

Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and ...
0
votes
1answer
38 views

Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum $k$-cut problem asks for a minimum weight $k$-cut. For $k=2$ this problem is P. Vazirani in ...
2
votes
1answer
30 views

Converting maximization to minimization in aproximation algorithms

Suppose algorithm A is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm. As you know it is enough to show Sol >= 1/2 OPT What I need to know is, ...
0
votes
0answers
45 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a ...
2
votes
1answer
144 views

2 approximation algorithm for the single machine scheduling problem

We are given one machine and $n$ jobs that we want to process. For the $n$ jobs we have the following data: $r_{1}, ... , r_{n}$ are the release times $p_{1}, ... , p_{n}$ are the processing times ...
2
votes
0answers
40 views

Aprroximation scheme for Multiple Choice Knapsack

In the paper FAST APPROXIMATION ALGORITHMS FOR KNAPSACK PROBLEMS (E Lawler 1979) gives a FPTA( Fully Polynomial time Approximation ) for multiple choice knapsack problem(MKP) . But MKP being strongly ...
4
votes
1answer
41 views

Hardness of a special GAP-CLIQUE problem

In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be ...
3
votes
0answers
41 views

Convex optimization with the help of Multiplicative Weights Update Method

I've already asked this question over at MathExchange, but since I received no replies or comments there, I hoped it might be more adequately fitting in this category. I have a convex (concave) ...
1
vote
0answers
11 views

Ways to perform “batch” Approximate Member Queries efficiently

In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number ...
-1
votes
1answer
30 views

How to check the ability to satisfy demand?

We have Stocks in several discrete positions, let say: A B C 40 20 80 And Demand, which may be satisfied by one or more Stock positions (if no specified ...
1
vote
0answers
37 views

Prerequisites for Approximation Algorithms [closed]

I'm new here, so I apologize if this is not the appropriate place to ask this question. I just started a graduate level course on approximate algorithms, and I am falling behind fast. The class is ...
1
vote
1answer
25 views

Term clarification: Establishing a domination

In the book "Approximation Algorithms" by Vazirani (legally available online), part of the hint to Exercise 9.6 (on page 77 of the book, page 95 of the PDF) says "Establish a domination". I've never ...
1
vote
1answer
29 views

How to determine approximability of a problem when we don't know how good a solution is?

As far as I have learned, an approximation algorithm for an optimization problem Runs in polynomial time, and Whose cost can be bounded by a function of input in terms of distance from the optimal ...
2
votes
0answers
28 views

Tight examples: Feedback vertex set 2-approximation algorithm

The specific algorithm I am referring to is Algorithm 6.8 from Vazirani's book "Approximation Algorithms". The book is legally available online here, and the algorithm is on page 58 (76 in the pdf). ...
5
votes
1answer
35 views

Why are PTAS-Reductions used to establish APX-Hardness?

What's the intuition for PTAS reductions instead of approximation preserving reductions or something of that ilk? I'd expect APX-Hardness to mean something like "finding a constant factor ...
2
votes
2answers
98 views

Minimising sum of consecutive points distances Manhattan metric

I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points ...
0
votes
1answer
217 views

Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
4
votes
0answers
109 views

2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
2
votes
1answer
79 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also ...
3
votes
0answers
46 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
0answers
29 views

Does the vehicle routing problem and variations have approximation ratios or a PTAS?

This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, ...
1
vote
2answers
35 views

Do Approximation Algorithms Analyzed in the Worst Case?

From wikipedia: For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is ...
3
votes
1answer
52 views

How can an approximation ratio be less than 1?

A question in my algorithms text-book requires that we, Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this problem. It is my understanding that $(1 - \frac{1}{k})$ ...
0
votes
1answer
88 views

approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality

I have the following question for the travelling salesman problem: The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, ...
4
votes
1answer
52 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
1
vote
1answer
127 views

Proof by induction concerning approximation algorithm for subset sum [closed]

Assignment question For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P_i$ that is at most the target sum $T$, there is a $z \in L_i$ such that ...
1
vote
1answer
43 views

Simple example: 2-approximation for vertex cover

I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation: Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to ...
0
votes
0answers
19 views

Is there a good model of computation for real numbers? [duplicate]

/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms. The integer numbers case Many algorithms use integers and their ...