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

144 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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$....
1 vote
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)$, ...
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$ ...
1 vote
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 ...
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$...
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 ...
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 ...
1k views

### Approximating $e$ with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to $e$ as possible? For example: ...
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 ...
1 vote
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$ ...
1k views

### Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
1 vote
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 ...
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?
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 ...
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 ...
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 ...
1 vote
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)...
26 views

1 vote
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-...
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 ...
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. ...
1 vote
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 (...
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 ...