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
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})\...
Manfred Weis's user avatar
  • 12.6k
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 ...
ReverseFlowControl's user avatar
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 ...
bonhomme's user avatar
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 ...
li ang Duan's user avatar
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} $$ ...
AnNam's user avatar
  • 1
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 ...
Mathematician....'s user avatar
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 ...
πr8's user avatar
  • 688
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} :=...
Display name's user avatar
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)=...
brant's user avatar
  • 43
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 + ...
Martin Clever's user avatar
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 $...
Simón Flavio Ibañez's user avatar
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 ...
Jackson's user avatar
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 ...
Adi's user avatar
  • 1
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 ...
Reflecting_Ordinal's user avatar
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 ...
Yossi Peretz's user avatar
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=...
cbyh's user avatar
  • 143
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Seb's user avatar
  • 3
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 ...
JanHula's user avatar
  • 13
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 ...
can't stop me now's user avatar
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 ...
Hemraj Raikwar's user avatar
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$....
cbyh's user avatar
  • 143
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)$, ...
Manfred Weis's user avatar
  • 12.6k
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$ ...
cbyh's user avatar
  • 143
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$...
lchen's user avatar
  • 459
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 ...
lchen's user avatar
  • 459
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 ...
lchen's user avatar
  • 459
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 ...
aroyc's user avatar
  • 221
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$ ...
lchen's user avatar
  • 459
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 ...
MadBlack's user avatar
  • 111
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?
lchen's user avatar
  • 459
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 ...
Xin Zhang's user avatar
  • 1,130
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 ...
Pierre's user avatar
  • 171
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 ...
NN2's user avatar
  • 250
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)...
Root's user avatar
  • 71
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: $$ ...
ABIM's user avatar
  • 5,047
-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 ...
Faré's user avatar
  • 99
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 ...
lchen's user avatar
  • 459
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 ...
Epsilon Away's user avatar
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 ...
lchen's user avatar
  • 459
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/...
AHQ's user avatar
  • 21
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}} & & \...
Manuel Madeira's user avatar
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 $...
lchen's user avatar
  • 459
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$ ...
lchen's user avatar
  • 459
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 ...
Iosif Pinelis's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
lchen's user avatar
  • 459
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$}? $$
ABIM's user avatar
  • 5,047
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-...
Venugopal K's user avatar
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. ...
user1775614's user avatar