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.
174 questions
1 vote
0 answers
89 views
How to give an efficient mappings for Hamming Distance?
Problem Statement: Consider two parties, a Sender holding a binary vector $s_1 \in \{0,1\}^d$ and a Receiver holding a binary vector $r_1 \in \{0,1\}^d$, where $d$ is the dimension and $\delta \geq 1$ ...
- 19
2 votes
1 answer
483 views
Comparing two adjacency matrices for graph equality
I'm currently working on a project that partially involves graphs. One of the problems I'm tackling is determining whether two given matrices represent the same connected undirected graph. So given ...
- 45
1 vote
0 answers
43 views
Planar Convex Hull given oracle confiming shape
Given two intervals $ X = [x_{min}, x_{max}], Y = [y_{min}, y_{max}]$ and an function $f: X\times Y\rightarrow \{0,1\}$ which confirms, whether a point is in or out of an unknown $k$-sided geometric ...
- 11
0 votes
0 answers
114 views
LLL algorithm for $\mathbb{Z}[X]$-lattices
I understand the LLL algorithm for finding approximate shortest vector in $\mathbb{Z}$-lattices (where the norm function is either $\ell_\infty$ or $\ell_2$), as well as finding the shortest vector in ...
0 votes
0 answers
150 views
Fast Approximation Algorithm for Finding Largest Anti-Chain in a Finite Poset
Given a finite poset $(X, \prec)$ of size $n = |X|$, how efficiently can we compute a constant-factor approximation to the maximum antichain? It is well-known that the size of the largest antichain ...
- 662
2 votes
0 answers
117 views
Algorithm for optimal set partition
Given a function $f:2^{[n]} \to [0, \infty)$, the problem is to find a partition $\mathscr{P}$ of $[n]$ which maximizes $\sum_{S \in \mathscr{P}} f(S)$. I am also interested in the case where $\...
- 121
0 votes
1 answer
139 views
A variant of Knapsack problem
In the standard Knapsack problem, the objective is to maximize $\sum c_i x_i$. I encounter a variant where the objective is to minimize $\sum c_i a^{x_i}$ where $a\in(0,1)$ is a constant. I am looking ...
- 327
0 votes
0 answers
55 views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1
5 votes
1 answer
409 views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
- 53
1 vote
1 answer
423 views
Linear interpolation vs L2-projection
I'm reading the book "The Finite Element Method: Theory, Implementation, and Applications" by Larson and Bengzon. In the first chapters there are presented two methods for approximating ...
- 19
3 votes
0 answers
109 views
Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?
Let’s I have the following : 2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
- 129
1 vote
1 answer
230 views
Chebyshev approximation via iterated weighted least squares fits
I have the task of finding a Chebyshev approximation for a time-series; I want to check different types of functions, e.g. polynomials, rational functions, harmonics, etc. I know that the Remez ...
- 13.9k
2 votes
1 answer
174 views
Finding survivable paths with a set of vulnerable edges
Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ ...
- 327
0 votes
0 answers
161 views
A variant of Steiner tree
Consider a directed Steiner tree problem with a source node $s$ a set $T$ of terminals with the following constraint. For each node $v$ on the tree, we assign a branching value $b_v$ as follows. (1) $...
- 327
0 votes
0 answers
28 views
Finding parameters of best approximating recursion
Question: how can the initial values $\left(a[0],\,\dots,\,a[k-1]\right)$ and the coefficients $\left(c_k,\,\dots,\,c_0\right)$ be determined that solve $\min\limits_{a[0],\dots,a[k-1]\\ c_k,\dots,...
- 13.9k
1 vote
0 answers
118 views
In the modular exponentiation, as used with the adaptive root problem, how to chose the best base that will yield as few results as possible?
Let $n,m,w\in\Bbb N$ and $\lambda\in\Bbb P$ such that $w^\lambda \mod m = n$, with the requirements: $\lambda$ being a random large prime such as $w^\lambda > 2\times m$ $1 < n < m−1$. m is ...
- 129
2 votes
0 answers
174 views
How to know if a random natural number is a probable semiprime?
Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
- 129
5 votes
3 answers
467 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 ...
5 votes
2 answers
392 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 ...
- 109
0 votes
0 answers
122 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} $$ ...
- 1
3 votes
0 answers
102 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 ...
- 892
3 votes
1 answer
211 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} :=...
- 755
0 votes
0 answers
129 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)=...
- 63
1 vote
1 answer
304 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 + ...
- 157
0 votes
0 answers
75 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
266 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 ...
- 1
0 votes
0 answers
114 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 ...
- 1
0 votes
2 answers
358 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=...
- 143
2 votes
1 answer
110 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 ...
- 13.9k
0 votes
1 answer
43 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 ...
- 3
1 vote
2 answers
137 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 ...
- 13
1 vote
0 answers
73 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
76 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
83 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$....
- 143
1 vote
0 answers
73 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)$, ...
- 13.9k
2 votes
1 answer
207 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$ ...
- 143
4 votes
1 answer
181 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$...
- 327
1 vote
0 answers
143 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 ...
- 327
2 votes
0 answers
83 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 ...
- 327
2 votes
0 answers
112 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 ...
- 221
1 vote
1 answer
108 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$ ...
- 327
1 vote
1 answer
238 views
Heuristics for lightweighted "cubic" spanning trees
I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-...
- 13.9k
1 vote
0 answers
148 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 ...
- 111
7 votes
1 answer
207 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?
- 327
2 votes
1 answer
144 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 ...
- 1,210
0 votes
0 answers
52 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 ...
- 171
4 votes
0 answers
373 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 ...
- 250
1 vote
0 answers
66 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)...
- 71
3 votes
0 answers
59 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: $$ ...
- 4,942
-5 votes
1 answer
210 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 ...
- 99