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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 views

Can we talk about approximation when the decision problem for solution existence is NP-Hard

I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
1 vote
0 answers
52 views

Find a cut of a graph that minimizes the ratio between the edge weights of the cut and the edge weights inside one subgraph

Given an edge-weighted undirected graph $G=(V,E)$ (can assume the weights are non-negative) and a source node $v_s\in V$, a cut is a partition of $G$'s vertices into two complementary sets $S$ and $T$....
1 vote
0 answers
44 views

What is an approximation algorithm in the context of NP completeness in general

In theorem 4 of Approximability of Minimum-weight Cycle Covers Bodo Manthey proves that: Then no approximation algorithm for $\operatorname{Min-L-DCC}$ achieves an approximation ratio of $o(n)$, ...
2 votes
1 answer
53 views

Longest path on directed acyclic graph when the weight is defined on the pair of edges

Given a directed acyclic graph $G=(V,E)$ with a source node $s$ and a sink node $t$, and we have a weight function that is defined on $E\times E$, $f:E\times E\to R^{+}$. We want to find a $s$-$t$ ...
1 vote
0 answers
117 views

Steiner tree subject to non-trivial constraint

Given a edge-weighted transportation network modeled as a graph. A source node $s$ needs to send an object to a set of $k$ destination nodes $t_i$, $1\le i\le k$. For the transportation, $s$ needs to ...
4 votes
1 answer
123 views

How to find an optimal sequence of merging operations?

Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$...
0 votes
0 answers
53 views

Graph reduction and combinatorial optimization

Crossposted at Theoretical Computer Science SE We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
2 votes
0 answers
44 views

Maximize connectivity probability with a number of edges

We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
6 votes
4 answers
1k views

Approximating $e$ with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to $e$ as possible? For example: ...
2 votes
0 answers
75 views

Is identifying the best in randomly chosen $n$ elements, equivalent to identifying one from the best half of randomly chosen $2n$ elements?

Suppose we are given a set $U$, and a black-box objective function $f: U \mapsto [0, 1]$. The job is to maximise $f(\cdot)$. Now, for a given $\delta \in (0,1)$, consider the following randomised ...
1 vote
1 answer
54 views

Steiner tree subject to edge capacity constraint

Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ ...
5 votes
1 answer
1k views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
1 vote
0 answers
43 views

Evaluate the goodness of piecewise linear approximation of a cubic Bézier [closed]

I saw that there are different algorithms for piecewise linear approximation of cubic Bézier curves out there. Now suppose that these algorithms can be either used interchangeably or that the ...
7 votes
1 answer
150 views

Metric TSP with integer edge cost

Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
0 votes
0 answers
34 views

Approximabilty of submodular over modular maximization

Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
2 votes
1 answer
87 views

What is the complexity of a special multigraph edge coloring problem

Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at ...
4 votes
0 answers
179 views

Approximation of integral of gaussian function over a parallelepiped

Remark: I posted this question in math stackexchange here and computer science stackexchange https://cs.stackexchange.com/ few weeks ago but obtain no answer. Given a multi-dimensional gaussian ...
1 vote
0 answers
37 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
0 answers
26 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: $$ ...
2 votes
0 answers
397 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/...
-5 votes
1 answer
129 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
1 answer
108 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 ...
6 votes
3 answers
466 views

Approximating derivatives between gridpoints

Suppose we have a grid (possibly irregular) of $N$ function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more). What would be a good way to ...
5 votes
1 answer
373 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
0 answers
59 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
0 answers
42 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 ...
2 votes
0 answers
102 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
0 answers
132 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
2 answers
175 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$ ...
7 votes
1 answer
531 views

Norms of B-spline coefficients

In Shumaker's book (Spline Functions: Basic Theory), we know that the $l^\infty$-norm of B-spline coefficients is bounded above and below by the $L^\infty$-norm of the spline itself. Are there similar ...
3 votes
3 answers
121 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
2 answers
336 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
0 answers
187 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
1 answer
48 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
0 answers
72 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-...
6 votes
1 answer
286 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
1 answer
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
0 answers
138 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
2 answers
146 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
0 answers
80 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 &...
5 votes
1 answer
442 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
0 answers
283 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
3 answers
385 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
0 answers
81 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
0 answers
91 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
1 answer
265 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 ...
3 votes
3 answers
653 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 ...
1 vote
0 answers
98 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 ...
3 votes
2 answers
3k views

Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
2 votes
0 answers
124 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 ...