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.

51 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
234 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 \...
6
votes
0answers
391 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 ...
5
votes
0answers
110 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 ...
5
votes
0answers
257 views

envelope function for a linear combination of gaussian distributions

Given a distribution $F$ defined as a linear combination of Gaussian distributions: $F = \sum_{i=1}^n C_i*N(\mu_i,\sigma_i)$ with $\sum_{i=1}^n C_i = 1$ I want to find a Gaussian function $Q = a*e^{\...
4
votes
0answers
168 views

Disjoint paths in temporal graphs

Given a graph $G=(V,E)$ and a pair of source-destination nodes $s$ and $t$. Time is divided in periods with the total number of periods denoted by $T$. Each edge $e$ is either operational or broken at ...
3
votes
0answers
23 views

Do higher-order splines with Lipschitz derivatives exist on finite sets?

Fix $k\in \mathbb{N}^+$ and let $E=(e_i,f_i)_{i=1}^I\subset \mathbb{R}^n\times \mathbb{R}^m$ be a non-empty finite set with $e_i\neq e_j$ whenever $i\neq j$. If $n=m=1$ then it's easy to see that: $$ ...
3
votes
0answers
450 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 ...
3
votes
0answers
238 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 ...
3
votes
0answers
209 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,...
3
votes
0answers
396 views

Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows: Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...
3
votes
0answers
70 views

Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
3
votes
0answers
178 views

A.G. Vitushkin's “Easily representable families of functions” - can it be generalized?

Background In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...
3
votes
0answers
241 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}( ...
3
votes
0answers
215 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
0answers
82 views

How to solve a QCQP where constraints are balls?

I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$ \begin{equation} \begin{aligned} & \underset{\theta}{\text{minimize}} & & \...
2
votes
0answers
120 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 ...
2
votes
0answers
109 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) =...
2
votes
0answers
482 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 ...
2
votes
0answers
90 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 ...
1
vote
0answers
31 views

Computational complexity of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
1
vote
0answers
53 views

Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?

Sorry for the verbose title, but the question is super specific. If you happen to know a site better suited for these types of question, feel free to direct me. The article to which I am referring to ...
1
vote
0answers
79 views

what is the computational complexity of Louvain algorithm?

I am not able to find out the computational complexity of the Louvain Algorithm. Can anyone here help me? link of the paper given below: DOI: 10.1088/1742-5468/2008/10/P10008 https://doi.org/10.1038/...
1
vote
0answers
128 views

Minimum delay path in time-dependent graph

Given a time-dependent graph, where each edge $e$ is on for certain time intervals and off otherwise. Traversing $e$ incurs a delay $d_e$ and is possible only when $e$ is on. Given a pair of vertices $...
1
vote
0answers
41 views

Meaning of L-reduction from Dominating set problem

We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-...
1
vote
0answers
137 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 (...
1
vote
0answers
64 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....
1
vote
0answers
90 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 ...
1
vote
0answers
76 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 ...
1
vote
0answers
100 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 ...
1
vote
0answers
202 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
vote
0answers
147 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 ...
1
vote
0answers
111 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
68 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 ...
1
vote
0answers
122 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 ...
1
vote
0answers
247 views

Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...
1
vote
0answers
74 views

An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (...
1
vote
0answers
259 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 ...
1
vote
0answers
532 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]$) ...
0
votes
0answers
25 views

Norm of vector components optimization of linear matrix combination

Given complex matrices $A_1, A_2, \dots, A_k\in\mathbb{C}^{m \times n}$, $B \in\mathbb{R}^{m \times n}$, the objective is to find a vector $x \in \mathbb{C}^k$ such that: $\max {||x_i||}$ , $i\in 1,2.....
0
votes
0answers
15 views

How to derive space bound for Morris(a) approximate counting algorithm

I was reading about Morris(a) here: https://www.cs.princeton.edu/~hy2/files/approx_counting.pdf. I was able to drive the expressions for $\hat{n}$ and Variance. But I am not able to derive the space ...
0
votes
0answers
41 views

A variant of travel salesman problem with charging points

Given a graph composed of a set $V$ of nodes, each representing a point to be visited by a salesman, and a set of fixed charging points. The salesman disposes a car that can travel $D$ distance before ...
0
votes
0answers
25 views

A variant of Steiner tree problem

Given a network modeled by a graph $G=(V,E)$, each edge $e\in E$ has a cost and a capacity. We seek a tree $T$ connecting a source (root) $s$ to $n$ destination vertices $d_1,\cdots,d_n$ minimizing ...
0
votes
0answers
70 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 &...
0
votes
0answers
39 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
74 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity \begin{equation} \sum_{k=1}...
0
votes
0answers
219 views

Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $\|f-G_m(f,D)\|>Cm^{-1/2}\lvert\{f}\...
0
votes
0answers
116 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 ...
0
votes
0answers
474 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 ...
0
votes
1answer
389 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...