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 ...
user avatar
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$....
user avatar
  • 143
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)$, ...
user avatar
  • 11.2k
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$ ...
user avatar
  • 143
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$...
user avatar
  • 521
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 ...
user avatar
  • 521
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 ...
user avatar
  • 521
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 ...
user avatar
  • 521
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 ...
user avatar
  • 201
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$ ...
user avatar
  • 521
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 ...
user avatar
  • 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?
user avatar
  • 521
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 ...
user avatar
  • 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 ...
user avatar
  • 171
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 ...
user avatar
  • 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)...
user avatar
  • 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: $$ ...
user avatar
  • 5,124
-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 ...
user avatar
  • 99
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 ...
user avatar
  • 521
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 ...
user avatar
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 ...
user avatar
  • 521
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/...
user avatar
  • 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}} & & \...
user avatar
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 $...
user avatar
  • 521
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$ ...
user avatar
  • 521
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 521
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$}? $$
user avatar
  • 5,124
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-...
user avatar
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. ...
user avatar
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 (...
user avatar
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 ...
user avatar
  • 521
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 &...
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
  • 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....
user avatar
  • 5,810
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....
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 572
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 486
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 ...
user avatar
7 votes
1 answer
357 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 ...
user avatar
2 votes
1 answer
304 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 ...
user avatar
  • 21
0 votes
0 answers
43 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 ...
user avatar
  • 3,698
2 votes
2 answers
227 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 ...
user avatar
1 vote
1 answer
911 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 ...
user avatar