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.
141
questions
1
vote
1
answer
37
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$ ...
- 113
4
votes
1
answer
122
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$...
- 503
1
vote
0
answers
116
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 ...
- 503
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 ...
- 503
0
votes
0
answers
52
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 ...
- 503
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 ...
- 201
1
vote
1
answer
52
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$ ...
- 503
1
vote
0
answers
40
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
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?
- 503
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 ...
- 1,002
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 ...
- 171
4
votes
0
answers
172
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 ...
- 215
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)...
- 71
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:
$$
...
- 5,008
-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 ...
- 99
2
votes
1
answer
106
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 ...
- 503
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 ...
- 111
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 ...
- 503
2
votes
0
answers
356
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/...
- 21
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 $...
- 503
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$ ...
- 503
3
votes
3
answers
120
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 ...
- 78.4k
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 ...
- 3,511
4
votes
0
answers
185
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 ...
- 503
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$}?
$$
- 5,008
1
vote
0
answers
70
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-...
- 11
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. ...
- 123
1
vote
0
answers
137
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 (...
- 1,173
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 ...
- 503
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 &...
1
vote
0
answers
280
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 ...
- 11
0
votes
3
answers
384
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 ...
- 3
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....
- 5,708
5
votes
1
answer
433
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....
user6671
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 ...
- 391
5
votes
1
answer
361
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 ...
- 51
1
vote
0
answers
95
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 ...
- 562
2
votes
0
answers
123
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 ...
- 22.7k
4
votes
1
answer
116
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 ...
- 12.9k
6
votes
1
answer
285
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 ...
- 466
3
votes
3
answers
643
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 ...
- 131
7
votes
1
answer
346
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 ...
- 937
2
votes
1
answer
303
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 ...
- 21
0
votes
0
answers
42
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 ...
- 3,698
2
votes
2
answers
225
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 ...
- 21
1
vote
1
answer
904
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 ...
user122122
5
votes
1
answer
264
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 ...
- 193
1
vote
2
answers
282
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 ...
- 31
1
vote
0
answers
101
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 ...
- 3,698