# Questions tagged [approximation-algorithms]

425 questions
Filter by
Sorted by
Tagged with
171 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) . So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
581 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 ...
68 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, ...
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 ...
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:...
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 ...
33 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 ...
84 views

567 views

104 views

### algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
260 views

### How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

I have these two problems: Problem 1 (Dual bin packing problem) Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$. Question: Find ...
101 views

### Percolation probabilities

I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others. I'm ...
125 views

### Weighted $l_1$ distance

So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
778 views

### Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or non-...
808 views

### Partial cover approximation

We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$. The ...
180 views

### Fast Approximation Algorithms for Covering Design

The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ ...
93 views

### About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
148 views

### Does k-PATH admit a constant approximation?

In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$. A $\alpha$-approximation for $k$-PATH is an ...
45 views

### Stochastic optimization with erroneous oracles

I am interested in a class of optimization problems of which we know that the input variable is first subjected to noise $\xi$ before entering the data-producing process $f$. I write the objective in ...
1k views

### Maximizing a monotone supermodular function s.t. cardinality

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this. Question: Is it known to be true or is there a hardness result ...
486 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 ...
243 views

### Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
116 views

### L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

Recently I read this paper which was published in FOCS2007. In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ...
333 views

### What is the reverse of greedy algorithm for setcover?

A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ...
701 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 ...
362 views

### Complexity of approximating the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$ I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
126 views

Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(... 1answer 232 views ### Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed? I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is: minimize$c^T \cdot x$, with$x\in \{0,1\}^n$and$c\in (\mathbb{Z}^...
Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...
### Approximation algorithms for the maximum $2$-independence set problem
I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...