# 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
Filter by
Sorted by
Tagged with
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. ...
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 (...
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 ...
66 views

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 &... 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 ... 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 ... 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.... 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.... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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) =... 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))=\... 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 ... 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. ... 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 \... 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 ... 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 ... 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 ... 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-... 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} ... 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 ... 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 ... 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 ... 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 ... 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 ... 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\... 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 ... 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 ... 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) ... 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 ... 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 ... 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. ... 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 (in general I would like to generalize to a more general case, but let's consider the easiest case ... 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 ... 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$...
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, ...