Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
425
questions
3
votes
0answers
44 views
Approximating a monotone submodular function using a concrete coverage function
Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e.
Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to ...
2
votes
1answer
214 views
Monotone supermodular function minimization under partition matroid constraints
Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?
4
votes
0answers
111 views
Learning hidden variable distribution
Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ...
3
votes
0answers
124 views
Stacks serving interval storage requests
An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
2
votes
0answers
96 views
Unbalanced connected partition
Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
14
votes
2answers
594 views
Proof assistant usage in complexity theory research?
Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most ...
0
votes
2answers
201 views
Geometric max cover
Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$.
Each point $p$ defines a set $B_p$ (or a ball) that covers all other points ...
1
vote
1answer
624 views
Common terminology used for lower/upper bounds
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
3
votes
0answers
114 views
On approximating problems in $\#P$
We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm
$\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
10
votes
1answer
402 views
Find an approximate argmax using only approximate max queries
Consider the following problem.
There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
2
votes
0answers
61 views
\alpha-path on Euclidean graphs
Consider the following problem:
Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
6
votes
0answers
156 views
Lower bound for Yao's algorithm on general addition chains?
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that
$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
1
vote
0answers
103 views
Hausdorff Distance and Convex Hull
Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
2
votes
0answers
63 views
On the impossibility of representing/approximating subadditive function using additive functions
I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \...
1
vote
1answer
121 views
Practical/heuristic algorithm for multi set-cover
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
3
votes
1answer
140 views
Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
1
vote
1answer
618 views
Clique cover problem
Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $...
0
votes
1answer
71 views
Approximating max degree $3$ perfect matching count?
We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.
What is the best factor in deterministic approximation schemes if we only care counting ...
5
votes
0answers
221 views
Why is HyperLogLog (near-)optimal?
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:
Clearly, maintaining $\epsilon$-approximate counts till ...
1
vote
1answer
115 views
hardness of constant approximation of largest matching set
We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.
Given a graph $G=(V,E)$ a subset $U\subseteq V$...
2
votes
0answers
175 views
Approximating the Radius of a (Dense) Graph
For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.
A $(1+\epsilon)$-approximating of APSP for a ...
1
vote
0answers
69 views
Sparse-cut approximation for well connected graphs
Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$.
If I understand UGC correctly, ...
2
votes
0answers
58 views
Studying the hardness of polynomial-time approximability using the concept of stability of approximation
In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that
Using the notion of stability one can ...
7
votes
0answers
112 views
Deterministic approximation algorithms for treewidth
As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
2
votes
0answers
104 views
Alternative Set Cover Algorithm With Doubling
I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:
Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:...
2
votes
2answers
340 views
Coreset and VC dimension
I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
4
votes
1answer
246 views
Looking for approximation class between NPO and Exp-APX
I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) ...
2
votes
0answers
34 views
Sparse coding and matching pursuit algorithms
Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
1
vote
0answers
84 views
Is it sufficient to only check on the vertices? Greedy algorithm
Suppose that I have a downwards closed Polyhedron and a vector $\omega$ and a greedy algorithm that goes as follows:
Given an initial $x_0$, order the indices of $\omega$. Then for each $i$, solve $\...
1
vote
0answers
61 views
What is known about data structures for encoding a set while considering approximate Rank queries?
Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$.
There are many data structures that allow storing $S$ while answering Rank ...
11
votes
2answers
4k views
Any fast algorithm for minimum cost feedback arc set problem?
In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.
If each edge is associated with a weight $w$, the minimum cost ...
7
votes
1answer
315 views
Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al
Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al;
my take of section IV.C. detailed description of KSVD, is ...
5
votes
0answers
202 views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
1
vote
0answers
873 views
Finding minimum weight $k$ cliques in a complete graph
For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar ...
3
votes
1answer
226 views
Compression algorithms for low-complexity strings?
Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there ...
3
votes
3answers
172 views
Approaches for Theoretical Analysis of Estimates of Probability Distributions
Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
1
vote
1answer
1k views
Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem
What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the ...
4
votes
0answers
332 views
What does “no integrality gap” imply?
I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale ...
45
votes
8answers
6k views
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
5
votes
1answer
742 views
Is there an approximation algorithm for MAX k DOUBLE SET COVER?
Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
1
vote
0answers
191 views
Maximize the weight of MST + sum of vertex weights
I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
3
votes
0answers
126 views
Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following ...
6
votes
0answers
180 views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
35
votes
3answers
4k views
Max-cut with negative weight edges
Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the ...
1
vote
0answers
118 views
Truthful posted-price mechanism with optimal efficiency (social welfare)
I am interested in mechanism design. In the paper On Profit-Maximizing Envy-free Pricing, SODA, 2005, the authors provided a truthful competitive posted-price mechanism with $4\log h$ guarantee of ...
3
votes
0answers
143 views
Maximize number of edges covered by an independent set of vertices
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
1
vote
0answers
159 views
Algorithms to approximate a Riemann integrable function by a piecewise constant function
We know that any general function that is Riemann integrable can be approximated to arbitrary precision by piecewise constant functions. So in this regard, I was looking for references on algorithms (...
6
votes
2answers
267 views
Finding smallest context free grammar that generates a set of sets
Are there any results known about the size of smallest context free grammar that generates a set of sets?
That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
3
votes
0answers
308 views
Approximating the VM packing problem
In the wikipedia article on bin-packing it is stated that
A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
3
votes
2answers
488 views
Quantum complexity of maximum inner product search
Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$. Typically $k \ll m, n$ (many ...
