# 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.

162
questions

0
votes

0
answers

19
views

### Approximation with "quantile-constraints"

Question:
given:
$$\begin{align}&\phantom{=}\lbrace \left(x_i,y_i\right),\ x_i\in\mathbb{X}, y_i\in \mathbb{R}\rbrace_{i=1}^n\\
&\phantom{=}f: (x\in\mathbb{X},\,p_1,\dots,\, p_k\in\mathbb{R})\...

4
votes

3
answers

279
views

### How to recover integer part from known fractional root part?

Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...

0
votes

0
answers

33
views

### Rounding approach to scheduling problem in chapter 3 of The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys

Suppose we have $𝑚$ machines and $𝑛$ jobs that can start immediately, and we want to distribute jobs to minimize the longest processing time among all machines. For any $\epsilon=1/𝑘$ for some ...

5
votes

2
answers

342
views

### How expressive is $e^A$ in the sense of universal approximation?

For any real matrix $B\in\mathbb{R}^{n\times n},n\ge 2$ and precision $\varepsilon$, is there a real matrix $A\in\mathbb{R}^{n\times n}$ such that $\|e^A-B\|_F<\varepsilon$? ($F$ refers to ...

0
votes

0
answers

70
views

### Numerical method for mixed system of equations and nonlinear inequalities

I am currently encountering challenges in determining the solution method for the following system of equations and inequalities:
$$
\begin{aligned}
&F(x) = 0\\
&G(x) < 0\\
\end{aligned}
$$
...

0
votes

0
answers

45
views

### Approximation factor for TSP Algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...

2
votes

0
answers

36
views

### Discrete approximation of continuous determinantal point processes

(throughout, "DPP" denotes "Determinantal Point Process")
TL;DR: Discrete DPPs are straightforward to compute with, continuous DPPs less so. Can we approximate continuous DPPs well ...

3
votes

1
answer

128
views

### How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by
$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...

0
votes

0
answers

62
views

### Approximate solution problem of rank-one modification matrix secular equation

In Golub's paper , page 327,the eigenvalues of a rank-one modification of a $n\times n$ symmetric matrix can be computed by findng the zeros of the secular equation
\begin{equation*}
w(\lambda_j)=...

1
vote

1
answer

180
views

### Approximation for interpolation of harmonic numbers

I need a good approximations for $H_p$, for $p \in (0,1) \cap \mathbb{Q}$, the generalization of $H_n=\sum_{i=1}^n \frac{1}{i}$ to the real numbers.
I tried $H_p = p \sum_{k=1}^\infty \frac{1}{k (k + ...

0
votes

0
answers

41
views

### Educated guess for algebraic approximation

I found a very neat ancient hindi formula for approximating square roots using rational numbers. After doing some algebra on the formula, i came across with this recursive relation:
Given any number $...

0
votes

1
answer

146
views

### A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...

0
votes

0
answers

79
views

### Lagrange's interpolating polynomial

Let $f:[a,b]\rightarrow R$ be a function that is not $C^{(n+1)}$ on $[a,b]$ but its $n$-th derivative is a Lipschitz function? How does the Lagrange's interpolating polynomial formula change? How does ...

0
votes

0
answers

37
views

### Approximation algorithm for non-infinite diameter of sparse directed graph

There are some good approximation algorithms that compute the diameter of a sparse directed graph, for example, this one.
Consider a little variation of the definition of diameter: we rule out ...

0
votes

0
answers

16
views

### Is there any reference proving hardness of approximation results for Linear Integer Programming With restricted finite domain?

Given $m\times n$ matrix $A$ of integers and $m\times 1$ vector $b$ of integers, the problem of whether there exists an $n\times 1$ vector $x$ of integers, such that $Ax=b$ and $x\geq 0$?, is known to ...

0
votes

2
answers

182
views

### Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)

Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...

2
votes

1
answer

80
views

### Approximation with special partitions of unity

Question:
what can be recommended for calculating $f(x)$ that solves $\frac{f(x)}{f(x)+f(1-x)}\approx g(x)$ for $x\in[0,1]$?
I have tried comparing Taylor series, but they look intimidating and I ...

0
votes

1
answer

22
views

### Pairing optimisation w.r.t. a given function, or at least close to optimised

Suppose you have a set of objects X and a scoring function f (in which order does not matter; f(x,y) = f(y,x)) which works in the following way.
Passing a viable pair of these objects to the function ...

1
vote

2
answers

96
views

### Choosing $k$ different assignments of binary variables in order to capture the largest volume of the joint probability distribution

Assume you have $n$ independent binary variables $\{x_1,\dots,x_n\}$ and for each variable $x_i$ you know that its value is equal to $1$ with a probability $p_i$. I would like to enumerate the joint ...

1
vote

0
answers

52
views

### Functional approximation with derivatives

I am trying to solve a functional approximation problem.
Consider a set of measurements of a d-dimensional state $\mathrm x \in \mathbb{R}^d$, together with velocities $\dot{\mathrm x}$ and ...

0
votes

0
answers

44
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

62
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

55
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

160
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$ ...

4
votes

1
answer

133
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$...

1
vote

0
answers

123
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 ...

2
votes

0
answers

62
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 ...

2
votes

0
answers

78
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

64
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$ ...

1
vote

0
answers

79
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

169
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?

2
votes

1
answer

92
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 ...

0
votes

0
answers

36
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 ...

4
votes

0
answers

268
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

45
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

34
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

1
answer

145
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

132
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 ...

1
vote

0
answers

70
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

57
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

967
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/...

2
votes

0
answers

148
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

146
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

181
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

3
answers

127
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

343
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

202
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

50
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

91
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

1
answer

37
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. ...