Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
111 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 ...
3
votes
1answer
32 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 ...
5
votes
1answer
165 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 ...
2
votes
2answers
102 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
174 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
226 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 ...
0
votes
0answers
10 views

How to square the (approximate) model count of a cnf formula?

Suppose I have a cnf formula (say $F$ with $n$ solutions) and an approximate model counter which gives c-factor result (i.e. the actual count lies between $1/2^c$ to $2^c$ times the value returned). ...
2
votes
2answers
153 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
181 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
0answers
81 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
158 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
78 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
96 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
132 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))=\...
-1
votes
0answers
31 views

Truncation error of product and composition of functions?

I'm trying to solve the following problem numerically $$\int_0^a\alpha(x)\frac{dw(x)}{dx}\frac{d v(x)}{dx}dx.$$ For any $\alpha$,w and v functions of x. The problem is that I don´t know what the ...
3
votes
1answer
161 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
315 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
218 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
177 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
186 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
72 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
197 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
636 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
250 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
937 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
135 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
181 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 ...
0
votes
0answers
87 views

Finding a path crossing minimum number of distinct colors

Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. ...
2
votes
1answer
316 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
367 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
76 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
139 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
366 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
409 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
105 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
439 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. ...
8
votes
2answers
3k views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm(). According to ...
1
vote
0answers
97 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
55 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
586 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
252 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
32 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, ...
3
votes
0answers
340 views

Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor. Group TSP is defined as follows: Take a ...
9
votes
1answer
421 views

State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are ...
3
votes
0answers
204 views

Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...
3
votes
0answers
35 views

Solving a Certain Constrained Isoperimetric Approximation-Problem

This question is related to my question Differential Geometric Aspects of Rubber Bands, where I asked for a mathematical model of contracting rubber bands. In contrast to my former question, the ...
5
votes
0answers
105 views

Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.) For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...
1
vote
0answers
110 views

FPTAS for approximating the permanent of a matrix

My question concerns approximating permanent of an $n$-by-$n$ matrix. Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...
3
votes
0answers
192 views

Estimating the growth rate of nondeterministic finite automata

Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$? No,...