An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that ...

learn more… | top users | synonyms

3
votes
0answers
238 views

Place n telescopes on a sphere in R^d to see the whole sky

Where would one put $n$ telescopes on the surface of the earth to see the whole sky as well as possible ? Use the cosine metric to define how well we can see in direction $x$: $ \qquad \text{cansee}( ...
8
votes
1answer
516 views

How to evaluate binomial coefficients efficiently and as correctly as possible?

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer. The reason why I ask is ...
1
vote
0answers
233 views

Multiobjective semidefinite programming

Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$. There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is ...
5
votes
1answer
709 views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
5
votes
2answers
575 views

Getting started: combinatorial optimization for computer scientists

I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems. I have good knowleges of graphs, *-flow algorithms and so ...
0
votes
0answers
114 views

sparsest cut always has solution

Hi! How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset. Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
1
vote
1answer
245 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
1
vote
0answers
470 views

Representing vertices of a cube using linear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$. Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$) ...
2
votes
2answers
576 views

biggest cube problem (given set of bricks)

Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces. Problem: find the way of putting together those pieces to make a solid that contains biggest ...
5
votes
0answers
269 views

Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
4
votes
1answer
816 views

Searching for an inhomogeneous diophantine approximation algorithm

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, what is an algorithm that will provide coprime integers $a$ ...
0
votes
0answers
344 views

Approximate a piecewise linear path by a path with bounded curvature

I have a piecewise linear path in two dimensions (with finitely many pieces). I would like to approximate it by a curve whose radius of curvature is bounded away from 0 (i.e. I specify the bound a ...
1
vote
2answers
2k views

Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
4
votes
2answers
538 views

Set Cover:Greedy vs LP

Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks
3
votes
0answers
203 views

Algorithm for testing satisfiable fraction of linear equations mod 2

Hello Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...
2
votes
2answers
364 views

Approximation of conformal mapping as a sum of elementary conformal mappings

Hi, I would like to approximate any 2d conformal mapping, as a sum of elementary conformal mappings. So I would have some basis, a conformal mapping with some parameters, and by adding several ones ...
5
votes
2answers
538 views

Runge-Kutta method with c<1

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...
6
votes
3answers
872 views

Approximating e with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible? For example: ...
4
votes
3answers
387 views

Approximating derivatives between gridpoints

Hi, Suppose we have a grid (possibly irregular) of N function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more). What would be a good way ...
0
votes
1answer
8k views

HOW TO Generate Equation of a Curve Given (x,y) pairs - algorithm? [closed]

Hi, How can I generate the equation of a curve that matches all arbitrarily given (x,y) pairs? I would like a polynomial of nth degree, where n does not matter, as long as the curve passes thru all ...
1
vote
2answers
670 views

Approximate Algorithms for Poisson's Equation (PDE)

Are there some approximate or randomised algorithms to numerically solve Poisson's Equation in Partial Differential Equations.(http://en.wikipedia.org/wiki/Poisson%27s_equation). The best algorithms I ...
4
votes
1answer
748 views

Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
1
vote
2answers
2k views

Analyzing Weighted Set-Cover variant

A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for ...