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.
132
questions
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)...
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:
$$
...
-5
votes
1answer
117 views
Lottery in O(1) per participant
Goal: implement in $O(1)$ per participant a lottery where each participant has some large number of tickets, and the best (e.g. least) one wins, without actually burning electricity in proportion to ...
2
votes
1answer
66 views
Min-sum and min-max node-disjoint path problems
Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
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 ...
1
vote
0answers
54 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 ...
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 ...
1
vote
0answers
81 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/...
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 ...
2
votes
0answers
83 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}}
& & \...
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 $...
0
votes
2answers
171 views
Minimal bottleneck path in time-varying graph
Given a graph $G=(V,E)$. The cost of each edge $e$ is a function of time, denoted by $w_e(t)$. Given a time interval $[0,T]$, for any path $P$ starting at $v_s$ at time $t\in[0,T]$, we denote $t_e^P$ ...
3
votes
3answers
113 views
Detecting slow growth in a finite number of queries
The following question was asked at Can you solve this problem using a finite number of queries?
:
Let $g:[0,1]\to[0,1]$ be a continuous monotonically-increasing function. You can access $g$ using ...
4
votes
2answers
328 views
Can you solve this problem using a finite number of queries?
Let $g:[0,1]\to[0,1]$ be a continuous monotonically-increasing function. You can access $g$ using queries of two kinds:
Given $x\in[0,1]$, return $g(x)$.
Given $y\in[0,1]$, return $g^{-1}(y)$.
Given ...
4
votes
0answers
174 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 ...
1
vote
1answer
47 views
Reference Request: Randomly Generated Contraction
Let $n_1>n_2\geq 1$ be integers. Are there a known algorithms for generating $n_2\times n_1$-dimensional random matrices $A$ such that
$$
\|Ax - Ay\|<\|x-y\| \mbox{ if $x\neq y$}?
$$
1
vote
0answers
43 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-...
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
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 (...
2
votes
2answers
140 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
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 &...
1
vote
0answers
248 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
341 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
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....
4
votes
1answer
393 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
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 ...
5
votes
1answer
253 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
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 ...
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 ...
4
votes
1answer
107 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
264 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
421 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
277 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
278 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
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 ...
2
votes
2answers
184 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
594 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
212 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
253 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
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 ...
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) =...
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))=\...
3
votes
1answer
179 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
536 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.
...
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 \...
1
vote
1answer
277 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
225 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
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 ...
3
votes
1answer
217 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-...
