Questions tagged [approximation-algorithms]

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 is within a constant factor of the optimum. Hardness of approximation is one way to separate NP-hard problems.

Filter by
Sorted by
Tagged with
2
votes
1answer
34 views

Subdividing a sequence such that sum is somewhat equally distributed

I have a sequence ( n, n-1, n-2,...,1). I need to find numbers in this sequence in this order that somewhat approximately divide it into M parts- within each M subgroup the sum is somewhat the same. ...
1
vote
0answers
130 views

Algorithmic combinatorial discrete problem (randomized lazy update?)

We are given a vector $\mathbf{b}$ of size $h$. Initially we have $\mathbf{b}_i=1$ for all $i\in \{1, 2, \ldots, h\}$. In a sequential fashion, at each time step $t=1, \ldots, n$, an index $j(t)$ is (...
2
votes
2answers
137 views

Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...
0
votes
0answers
66 views

Maximize sum of supermodular functions over nested sets

Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies: For all $t &...
1
vote
0answers
163 views

Adaptive Simpsons Quadrature Algorithm for Double Integrals? [closed]

I'm currently using Numerical Analysis 10th edition by Richard L Burden as a reference for approximate Integration techniques. In there it describes the Adaptive Simpsons Quadrature rule that inputs ...
0
votes
3answers
294 views

Im looking for an algorithm that can solve or approximate the solution to a problem

Let me first explain the problem using an analogy. Let's say you have $N$ doors and $M$ keys. Each door can be opened with a combination of keys, each combination is also unique (i.e. there aren't be ...
1
vote
0answers
45 views

Hutchinson-type algorithm for efficient computation of trace of inverse of non symmetric matrix

Let $A$ be an invertible $N$-by-$N$ matrix, for some large $N$ (say $N = 10^6$). Suppose the only thing we know how to do is apply $A$ to a vector, i.e compute matrix-vector products $Az$. Question....
4
votes
1answer
342 views

Fast Bourgain embedding (or similar embeddings)?

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www....
1
vote
0answers
87 views

What's the name of functions that produces a non deterministic solution without losing the exact solution?

I know that Turing reductions, function reductions and aproximation algorithms can produce good results and aproaches to the solution of a problem, but sometimes they lost the exact solution. Is there ...
5
votes
1answer
143 views

Row-based iterative algorithms for computing the kernel of a matrix

Suppose $A$ is an $m \times n$ matrix in the form $$A=\begin{pmatrix} — a_1 —\\ — a_2 —\\ \vdots \\ — a_m — \end{pmatrix}$$ where $a_i \in R^n$ is the $i$-th row of $A$. I know that it is possible ...
1
vote
0answers
62 views

How to compress variables in a linear regression

I have a large linear regression where all the independent variables are logical (ie TRUE/FALSE) and sparse. The data has roughly 10,000 variables and 10 million observations, on average around 20 ...
2
votes
0answers
118 views

Can one optimize the probability that an identity is satisfied until the probability is $1$?

I wonder how well one can obtain algebraic structures that satisfy interesting algebraic identities by simply slowly modifying those algebraic structures until they satisfy the required identities. I ...
4
votes
1answer
91 views

complexity of bounded knapsack with spoilage

Consider the usual bounded knapsack problem, with the extra twist: you know that $k$ of the chosen items will get spoiled after the sack is packed. And this happens adversarially, i.e. $k$ most ...
6
votes
1answer
250 views

Approximate homology of a large simplicial complex

I can use software to calculate the Betti numbers $\beta_0,\beta_1,\beta_2,\dots$ of a finite simplicial complex. This is prohibitive for large complexes, built on say > 100,000 nodes. Is there some ...
3
votes
3answers
246 views

Approximation of half-integers modified Bessel function of the second kind

I am trying to optimise the calculation of the probability distribution poisson-inverse-gaussian its calculation involves a half-integers modified Bessel function of the second kind. Here's a formula ...
7
votes
1answer
241 views

Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...
2
votes
1answer
262 views

The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to ...
0
votes
0answers
38 views

A name for algorithms that perform well in an asymptotic sense, when inputs are random

Is there a term for an algorithm that performs "well" (say, within a constant factor of optimality) in an asymptotic sense when a large number of random inputs are provided? For example, say I had an ...
2
votes
2answers
162 views

Fast Algorithms for sum of independent random variables

CLT implies the sum of n i.i.d random variables,after property normalized converge to a Normal distribution as n goes to infinity. Furthermore, Linderberg's condition points out not necessarily ...
1
vote
1answer
481 views

Removing the minimum number of edges to make a graph triangle-free (using set cover)

Assume that we are given a weighted, undirected graph $G = (V; E)$ where each edge $e \in E$ is assigned weight $w(e) \geq 0$. The goal is to remove a set of edges $D \subseteq E$ with minimum weight ...
5
votes
1answer
136 views

What is the LP gap of vertex cover in planar graphs?

What is the LP gap of vertex cover in planar graphs? The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $ $ c_e \geq 0 $ are ...
1
vote
2answers
224 views

A variation of longest paths in directed acyclic graph

Let $D=(V,A)$ be a simple directed acyclic graph, where $A$ is a set of arcs. Let $S$ be a subset of $\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$. The $S$-length of a path $P$ is ...
1
vote
0answers
97 views

Heuristics for this “subset” traveling salesman problem

Are there any known heuristics for the following variation of the traveling salesman problem: given $n$ sets of points $S_1,\dots,S_n$, and $n$ integers $k_i$ such that $k_i \leq |S_i|$, find the ...
2
votes
0answers
107 views

Is there an algorithm for numerical approximation of (naive) period integrals

Let $d$ be an integer, and let $f_1, \ldots, f_m$ and $g_1, \ldots, g_n$ in $\mathbb{Q}[X_1,\ldots,X_d]$ be rational polynomials. Then $$D = \{ (x_i)_{i=1}^d \in \mathbb{R}^d \mid f_j(x_1,\ldots,x_d) =...
1
vote
0answers
169 views

Can Carlsons's iterative algorithm for $\arctan x$ be inverted to get one for $\tan x$?

In the article An algorithm for computing logarithms and arctangents, by B. C. Carlson, the following iterative algorithm for arctangents is given: The algorithm uses that $2^n\tan(2^{-n}\arctan(x))=\...
3
votes
1answer
172 views

Is there a Fourier Analytic way to approximate volume?

Suppose a convex compact room in $3$-dimensions is given and source and microphones recorders are provided in the room that can locate echo timings there are works in literature which can give you the ...
10
votes
3answers
398 views

Approximate volume computation and lattice point enumeration - hardness

Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation. ...
6
votes
0answers
229 views

Quantum Optimization as approximating $\mathbb{CP}^{2^n -1}$ with the orbits of a subgroup of SU($2^n$)

For example given a great circle within the sphere, we can think about computing the average distance of a point on the sphere from the great circle. Slightly more generally, given a subgroup $H \...
1
vote
1answer
242 views

Are there any solvers to Chance Constrained Programming Problems

I'm trying to solve a chance constrained programming (CCP) problem $\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$ ...
3
votes
1answer
214 views

Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron

A centrally symmetric convex polyhedron in $\Bbb R^n$ shifted from the origin with possibly $e^{\alpha n}$ number of vertices at some $\alpha>0$ has an unique ellipsoid of maximum volume called ...
1
vote
0answers
102 views

3-Approximation Algorithm for Weighted 3-Hitting Set (Weighted Set Cover)

I need to find a 3-Approximation Algorithm for a weighted 3-Hitting Set. I have an 2-Approximation Algorithm for a weighted 2-Hitting Set and in its explanation the Hitting-Set-Problem is formulated ...
3
votes
1answer
212 views

computational complexity: do we gain acceleration?

There is a technique we developed for series acceleration using the Wilf-Zeilberger method. Here is a simple Maple code in this regard, you need to download this too. The idea is you start with a WZ-...
2
votes
1answer
892 views

3-Approximation Algorithm for 3-Hitting Set

I need to find a $3$-approximation algorithm for finding a $3$-hitting set. The set-up is that I have a set $S$ and a family $\mathcal{F}$ of subsets of $S$, where each member of $\mathcal{F}$ ...
2
votes
0answers
368 views

Inverse set cover problem

Given a universe $U$, and a set of subsets $S=\{S_i:S_i\subseteq U\}$, find $k$ such subsets so that their union size is minimal. Is there a name for this problem? Is it NP? Are there efficient ...
1
vote
1answer
2k views

2-approximation algorithm for Minimum Maximal Matching (MMM) problem

I'm looking to find a 2-approximation algorithm (pseudocode) for the minimum maximal matching problem. I tried to find one but I did not manage. I want to use it to implement a program in java. Can ...
1
vote
1answer
287 views

Approximating a function with sums of gaussians

For an application I have to approximate a continuous (and hopefully smooth) positive even function that decays at infinity with a sum of sums of gaussians, preferably orthogonal ones. That is, a ...
0
votes
1answer
205 views

Finding a subgraph of cliques with the minimum total sum weight

Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
2
votes
1answer
389 views

Complementary slackness for approximately optimal Dual solution

Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
6
votes
1answer
415 views

Algorithm to compute Matrix Sign Rank?

The (generalised) sign-rank of a (generalised) sign pattern $S\in \{+,-,0\}^{n\times m}$ is the minimum rank of all matrices with the same sign pattern, i.e. $$ \min\left\{\operatorname{rank}(M)\ :\ M\...
2
votes
0answers
89 views

Relationship between weight of spanning tree in a tree metric approximation and the original metric

So suppose we have a tree metric which approximates the Euclidean distance between a finite set of points. The leaves correspond to points in the original space. It may be an ultra metric, and ...
2
votes
2answers
161 views

Need a graph theory problem with nontrivial faster approximation algorithm

A friend of mine who has done some work in approximation algorithm asked me the following question: Can you find a (graph theory) problem with a faster approximation (deterministic) algorithm? For ...
0
votes
2answers
428 views

Relaxed path decomposition of a graph

Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
8
votes
1answer
436 views

Polynomial approximations of curves

This is the 3D version of this question. The responses to that question contained a lot of complaints about fuzzy definition of the problem, so I made this new question very narrow and explicit. For ...
2
votes
1answer
127 views

Bounds on the positive roots of a bivariate polynomial

It is well known that various real root isolation methods are based on computing, first, the bounds on the values of the positive real roots of a polynomial equation. For the univariate case such ...
2
votes
2answers
621 views

How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...
1
vote
0answers
110 views

Asymptotic determinant of $2\times 2$ Toeplitz matrix

The problem that I am dealing with is to compute the determinant of a $2\times 2$ Toeplitz matrix[1] (in general I would like to generalize to a more general case, but let's consider the easiest case ...
1
vote
0answers
64 views

Matrix Completion: Clearing Step

I am trying to implement Keshavan, Montanari and Oh (2009) algorithm for Matrix Completion. It consists of three steps: 1) Trimming which nulls some rows and columns to make the high singular values ...
18
votes
2answers
653 views

“Fractally self-similar” numbers

This is another question about visualization of Ford circles, the previous one being Confusion with practically implementing rational approximations. Here is an output of zooming into Ford circles at $...
10
votes
1answer
264 views

Confusion with practically implementing rational approximations

Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
1
vote
0answers
33 views

Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph. I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...