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.
114
questions
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, ...
