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

learn more… | top users | synonyms (1)

2
votes
0answers
11 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
44 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 ...
2
votes
0answers
39 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
22 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
33 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
36 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
56 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
48 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
99 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
31 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 ...
3
votes
0answers
53 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
1
vote
1answer
96 views

What is known about this TSP variant? [closed]

This question was cross-posted to cstheory.SE here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of ...
1
vote
0answers
14 views

A query regarding the Max3SAT Approximation Algorithm's Application

Its known that a polynomial time Approximation Algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. If given that the given 3MaxSAT is satisfiable, it is still difficult to find a 7/8+e ...
2
votes
1answer
39 views

Is it possible that low-resource Turing Machines can always “usually” agree with high-resource Turing Machines

Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs. It is known that there are problems in ...
1
vote
1answer
69 views

Seeking Efficient Approximation Algorithm for Adaptation of TSP

Consider the following adaptation of the traveling salesman problem: Given a complete, undirected graph $G$ with nonnegative edge weights, color each vertex either red or blue. Find the shortest ...
4
votes
1answer
56 views

Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that: For any $\epsilon >0$, there are probabilities for which the ...
1
vote
1answer
61 views

Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
5
votes
1answer
35 views

Maximizing the minimum of $k$ submodular functions

Let $f(X)$ be a monotone submodular function from $2^{\{1, \ldots, n\}}$ to $\mathbb{N}$ and consider the problem of maximizing it subject to a cardinality constraint $|X| \leq m$. By using the greedy ...
-1
votes
1answer
149 views

Approximating the diameter of graph G

Anyone has an idea how to solve this problem: Let G be an undirected, unit-weighted connected graph. Design a linear-time algorithm to obtain a 2-approximation of the diameter of G. I.e., the largest ...
0
votes
0answers
18 views

From hypercontractivity norm bounds to small set expansion property

Consider these two theorems on this theme, Lemma 8 on page 10, http://www.boazbarak.org/sos/files/lec2d.pdf Lemma B.1 on page 63 of http://arxiv.org/pdf/1205.4484v3.pdf Aren't these two theorems ...
0
votes
1answer
15 views

Is there an implicit condition OPT<P(|input|) in approximation schemes?

Sorry if my question is banal. Consider an approximation scheme such as FPTAS that guarantees to find a soln>(1-eps)OPT for ...
3
votes
1answer
88 views

Greedy algorithm for Set Cover problem - need help with approximation

I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above. ...
1
vote
0answers
20 views

FPTAS for knapsack with private valuations

The Knapsack problem has a well-known FPTAS based on rounding and then using the pseudopolynomial dynamic programming algorithm. When the valuations $v_i$ are private, we also need the assignment rule ...
2
votes
0answers
59 views

How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances. I ...
17
votes
3answers
1k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
6
votes
1answer
62 views

Mathematical optimization on a noisy function

Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x ...
1
vote
0answers
33 views

Reference for approximation algorithms [closed]

what is the best book to gain an introductory understanding of approximation algorithms? I'm looking for something along the lines of the Sedgewick, that has examples written in a well known language ...
1
vote
1answer
41 views

Perturbation of a vector

Given a vector $x=(x_1,\cdots,x_n)$ such that $0\leq x_i \leq1$ and $\sum_{i=1}^n x_i=1$. I would like to find a vector $x^*$ such that ($l_1$ norm ) $||x-x^*||_1\leq \delta$, where $\delta >0$. ...
9
votes
2answers
125 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
0
votes
1answer
63 views

Sorted-greedy for Load Balancing Problem

In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of ...
-1
votes
3answers
49 views

Can approximation help find the exact answer?

Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in ...
1
vote
1answer
82 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
1
vote
1answer
100 views

Subset-sum approximation algorithm running time

in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$ Essential part of this algorithm is trimming. On every step you delete all numbers which close ...
1
vote
1answer
164 views

3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the ...
1
vote
0answers
17 views

MaxSNP flow problems

Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
0
votes
1answer
94 views

Approximate the order of summation of two vectors

Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ ...
3
votes
1answer
44 views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
3
votes
1answer
191 views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which ...
1
vote
0answers
43 views

Approximation for fewest incompatibilities in a scheduling algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
3
votes
1answer
105 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
2
votes
1answer
31 views

Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
1
vote
2answers
116 views

A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
2
votes
1answer
49 views

Proving approximation ratio

We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking ...
1
vote
1answer
28 views

Hardness and approximation of a problem with a parameter

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could ...
0
votes
2answers
40 views

What all can a valid approximation algorithm access?

For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?
0
votes
0answers
58 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 ...
2
votes
1answer
64 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
11
votes
3answers
1k views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
4
votes
1answer
42 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...