Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

17
votes
0answers
359 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 ...
16
votes
0answers
612 views

Practically Good Algorithms of a Very Low Computational Complexity Class

I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties: 1) Solving the ...
16
votes
0answers
410 views

Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
14
votes
0answers
491 views

Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)

Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same. First, I will define a few ...
12
votes
0answers
301 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
11
votes
0answers
287 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
9
votes
0answers
232 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of $\...
9
votes
0answers
248 views

Additive error in counting the number of 1's in a sliding window?

The setting is as follows: We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
9
votes
0answers
244 views

Approximating a convex polyhedron, with fewer inequalities

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words, $$\mathcal{...
8
votes
0answers
99 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
8
votes
0answers
216 views

Complexity and approximability of maximum edge biclique problem on co-comparability graphs

A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph. Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete ...
8
votes
0answers
156 views

Is the dominating set problem constant-factor-approximable in undirected path graphs?

I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class. A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
8
votes
0answers
361 views

Efficiently approximating derivative of a well-behaved function

I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
7
votes
0answers
101 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 ...
7
votes
0answers
159 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 ...
7
votes
0answers
204 views

Minimum weight expander

Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
7
votes
0answers
607 views

Hardness of Approximation results for Special Set Packing Problem Wanted

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem? The general Set Packing Problem would be: Given A Collection of ...
7
votes
0answers
535 views

Difference between Primal Dual Algorithm for Proper and Uncrossable Functions

Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions: (1) super-modular functions (2) proper functions ...
7
votes
0answers
250 views

Results regarding Bounded Diameter Minimum Spanning Tree

Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of ...
7
votes
0answers
140 views

log(OPT) approximation for directed balanced vertex separator

Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of ...
6
votes
0answers
110 views

Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
6
votes
0answers
125 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 ...
6
votes
0answers
214 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 ...
6
votes
0answers
197 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 ...
6
votes
0answers
166 views

Statistical Algorithms vs Convex Relaxations - Planted Clique

I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
6
votes
0answers
279 views

Bipartite vertex separator

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...
6
votes
0answers
594 views

Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
5
votes
0answers
143 views

Classification of randomized approximation algorithms

Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ...
5
votes
0answers
105 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 ...
5
votes
0answers
105 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
5
votes
0answers
242 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 ...
5
votes
0answers
220 views

Is MAX-SAT SETH (like) hard?

If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy. There ...
5
votes
0answers
112 views

The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
5
votes
0answers
103 views

Maximizing a submodular function with restricted values

Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$. I am wondering if a better approximation algorithm exists if the ...
5
votes
0answers
333 views

Tuning Parameters of Locality Sensitive Hashing

We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
5
votes
0answers
166 views

Approximate c-chromatic number, each color class is P4-free (cograph)

The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
5
votes
0answers
130 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize the quantity \begin{equation} \sum_{k=...
5
votes
0answers
397 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
5
votes
0answers
160 views

Online Interval Coloring Problem

We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $...
5
votes
0answers
207 views

On the optimal solution of the CKR formulation for MULTIWAY CUT

Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
5
votes
0answers
74 views

A question regarding Improved Algorithm for Degree Bounded Survivable Network Design Problem

In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis, have used the iterated rounding approach in a similar as by Jain in designing the ...
5
votes
0answers
126 views

Finding an index set so that row sums are positive

Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of ...
4
votes
0answers
38 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 ...
4
votes
0answers
123 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 ...
4
votes
0answers
128 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 ...
4
votes
0answers
481 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just $\...
4
votes
0answers
82 views

Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
4
votes
0answers
176 views

Size of Independent set of sparse graphs with few triangles

Notations $\alpha(G) = $ Max sized independent set of graph $G$. $n(G) = $ Number of vertex in graph $G$. Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$, $$\...
4
votes
0answers
152 views

Find index set partition that has large projections

I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
4
votes
0answers
256 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 ...