Skip to main content

Questions tagged [approximation]

Questions about algorithms that solve problems up to some bounded error.

188 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
0 answers
162 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
Michael's user avatar
  • 580
8 votes
0 answers
214 views

Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
Narek Bojikian's user avatar
8 votes
0 answers
91 views

Connections between circuit complexity and Unique Games Conjecture?

Circuit complexity has connections to many questions in complexity theory. For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
Andrew's user avatar
  • 286
8 votes
0 answers
1k views

Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)

If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem? (...
user1464's user avatar
6 votes
1 answer
122 views

A dynamic program to decide whether the solution is in a given range

In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. The problem can be ...
Erel Segal-Halevi's user avatar
5 votes
0 answers
122 views

Minimum spanning tree and Hamiltonian path

For a graph $G(V,E)$, under what conditions is a minimum spanning tree of $G$ equal to a hamiltonian path on $G$? IS there any body of literature connecting these two?
Vivek Bagaria's user avatar
5 votes
0 answers
710 views

2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
Harry's user avatar
  • 111
4 votes
0 answers
76 views

Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph

I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible. The problem is quite simple: Given $G = (V, E)$ an undirected graph, ...
Manel Rosana's user avatar
4 votes
0 answers
50 views

K-means, but normalized and with max

Given points $x_1, \ldots, x_n$ in the Euclidean space and $K \in \mathbb N$, I'm interested in the following objective. Partition the points into $K$ clusters $C_1, \ldots, C_K$ so that: $$\max_{i \...
Dmitry's user avatar
  • 345
4 votes
0 answers
37 views

What is a term for a problem that is hard to approximate within a factor $c$?

Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
Erel Segal-Halevi's user avatar
4 votes
0 answers
63 views

Universal approximation bounds of the form $\|f(x)-\hat{f}(x;w)\|\leq \varepsilon \|f(x)\|$

It is known that for every $\varepsilon>0$ there is an appropriate neural network architecture, such that one can approximate any continuous function $f:[0,1]^n\to[0,1]^m$ by the neural network ...
FeedbackLooper's user avatar
4 votes
0 answers
122 views

Approximation algorithms for indefinite quadratic form maximization with linear constraints

Consider the following program: \begin{align} \max_x ~& x^TQx \\ \mbox{s.t.} ~& Ax \geq b \end{align} where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise ...
cangrejo's user avatar
  • 168
4 votes
0 answers
67 views

Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
Puzzled's user avatar
  • 41
4 votes
0 answers
68 views

Randomized algorithm to compute cover radius?

I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it. Let $C$ and $P$ be two sets of point in the plane , such ...
ShaoyuPei's user avatar
  • 153
4 votes
0 answers
112 views

Intuition for vertex/set cover approximation algorithms

The best approximation algorithm for vertex cover is randomly choosing an edge and removing its vertices (picking the largest degree vertex actually is a worse approximation), but the best ...
Jess's user avatar
  • 141
4 votes
1 answer
114 views

Approximation algorithm with runtime complexity between poly(log(1/eps)) and poly(1/eps)?

Suppose we have an approximation algorithm to some maximization problem, that returns a solution with value $(1-\epsilon)*OPT$. If the runtime of the algorithm is polynomial in the input size and $1/\...
Erel Segal-Halevi's user avatar
3 votes
0 answers
42 views

Approximation of the Normal Set Basis Problem

Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$. The input of ...
Bader Abu Radi's user avatar
3 votes
0 answers
74 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
df21's user avatar
  • 63
3 votes
1 answer
424 views

Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
Null_Space's user avatar
3 votes
0 answers
35 views

Estimating number of points in 1D space

There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
sbterr's user avatar
  • 31
3 votes
0 answers
61 views

Approximate algorithms for class P problems

As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
Alireza Farahani's user avatar
3 votes
0 answers
36 views

Rearrange items in order reduce fragmentation and reduce wasted space

I have a segment with some offsets at irregular intervals There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset. Items are free ...
Elia Perantoni's user avatar
3 votes
0 answers
191 views

Is there an optimization problem on planar graphs which is APX-hard ?

I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
Mathieu Mari's user avatar
3 votes
0 answers
188 views

Why gap preserving reduction is weaker than L-reduction?

In Vizirani's textbook says in page 332, Gap preserving reductions are weaker than their L-reductions [...] one of the motivations for the PCP theorem was that establishing an inapproximability ...
user777's user avatar
  • 749
3 votes
0 answers
269 views

2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
Elisha's user avatar
  • 173
3 votes
0 answers
44 views

Incremental over-approximation of DAG reachability

I'm looking for a data structure that stores an approximation of a DAG: If a node $x$ is reachable from a node $y$ in the DAG, then it is reachable in the approximation. For a given fairly small root ...
fread2281's user avatar
  • 161
3 votes
0 answers
339 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
Nathan's user avatar
  • 31
3 votes
0 answers
177 views

Convex optimization with the help of Multiplicative Weights Update Method

I've already asked this question over at MathExchange, but since I received no replies or comments there, I hoped it might be more adequately fitting in this category. I have a convex (concave) ...
Checkmate's user avatar
3 votes
1 answer
108 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
Thomas Bosman's user avatar
3 votes
0 answers
294 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
R B's user avatar
  • 2,634
3 votes
1 answer
361 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
jam123's user avatar
  • 61
3 votes
0 answers
90 views

What functions are easy to optimize?

Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$...
Karolis Juodelė's user avatar
3 votes
1 answer
63 views

Packing unsplittable flows problem

For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ : Let's define as flow ...
Filippo Vitale's user avatar
2 votes
0 answers
51 views

Approximate the parity function in L1-norm

Consider the parity function $MOD_2(x) = x_1 \oplus \cdots \oplus x_n$ for $x \in \mathbb{F}_2^n$. I am concerned about the degree bounds for a real polynomial $f$ which approximates $MOD_2$ well in ...
TheGuy's user avatar
  • 21
2 votes
1 answer
128 views

Budgeted Independent Vertex Cover

Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
giochi's user avatar
  • 131
2 votes
0 answers
91 views

Finding a maximum induced DAG in a digraph

I have a digraph D on n vertices formed in the following manner: I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
Dave's user avatar
  • 71
2 votes
0 answers
45 views

Designing Shortest Route

Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
Sandra's user avatar
  • 63
2 votes
0 answers
71 views

State of the art implementations of minimum-cost multicommodity flow approximation algorithms

I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
fuglede's user avatar
  • 165
2 votes
0 answers
54 views

Optimal allocation of heterogeneous divisible goods

In the context of my PhD on the simulation of the labor market with a multi-agent model, I encoutered a problem that doesn't seem to be really treated in the litterature, according to my searches on ...
Nicinic's user avatar
  • 31
2 votes
0 answers
64 views

An approximation variant of the halting problem

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable. I have just thought of a variant approximation-...
nir shahar's user avatar
  • 11.6k
2 votes
0 answers
74 views

Total weight of all spanning trees

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
abhi01nat's user avatar
  • 141
2 votes
0 answers
50 views

Complexity of approximating a function value using queries

I am looking for information on problems of the following kind. There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
222 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
Tav's user avatar
  • 113
2 votes
0 answers
50 views

FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
Rupok Saha's user avatar
2 votes
0 answers
60 views

ln(n) + 1 Approximation for Set Cover constructions

Set Cover Problem: Given a set $X$ and a collection of subsets $S_1, S_2, \ldots S_m \subseteq S$, we want to find the smallest cardinality of a set of $k$ elements $\{i_1, \ldots i_k \}$ such that $\...
Tarang Saluja's user avatar
2 votes
0 answers
146 views

Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
galoosh33's user avatar
  • 121
2 votes
0 answers
92 views

Different properties of Heavy-Hitters and Count-Min Sketch algorithms?

I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
Max's user avatar
  • 251
2 votes
0 answers
118 views

An approximation for the sum of k largest elements of n-sorted arrays?

Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements. All elements are between 0 and 1, and the the sum of all elements in array $i$...
user3563894's user avatar
2 votes
0 answers
63 views

Hardness of approximation for online algorithms

Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds ...
Television's user avatar
2 votes
0 answers
582 views

Why is there no FPTAS for the maximum independent set problem?

I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$. I found the following approach after some ...
PlsWork's user avatar
  • 427