Stack Exchange Network

Stack Exchange network consists of 174 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-hardness]

Hardness of approximation, aka inapproximability.

3
votes
1answer
50 views

Distinguising between the cases of low or high cover number

Is there a known result saying that for some constants $0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover ...
6
votes
1answer
152 views

Does Max Planar 3-SAT admit a PTAS?

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
1
vote
0answers
55 views

Reasoning about NP hardness of optimization problems with closed form functions as input

(This may not be a research level question per se. I can delete this question if the community thinks this way too) I am trying to understand how to reason about hardness of optimization problems ...
4
votes
0answers
45 views

Inapproximability Results for APX-hard Geometric Optimization Problems

A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
8
votes
0answers
123 views

Which version of KAKUTANI does lie in PPAD?

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
0
votes
1answer
92 views

Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph. Input: Given a graph G with non-negative vertex weights and ...
2
votes
0answers
114 views

Hardness of Approximation for minimum path cover in an undirected graph?

Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
4
votes
0answers
34 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 ...
1
vote
1answer
534 views

Approximately counting paths and cycles in a graph

Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. The question is about the approximability of these graph ...
1
vote
0answers
87 views

Does the NP-hardness of finding any valid solution imply NPO-hardness?

Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
0
votes
0answers
357 views

APX-Hard vs NP-Hard

I am confused whether $\mathsf{APX-hard} \subseteq \mathsf{NP-hard}$. My confusion stems from a result on graph pricing from this paper which says the following : "Unlike the general case of the graph ...
3
votes
0answers
104 views

Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", ...
5
votes
0answers
103 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 $$\...
1
vote
1answer
196 views

Is there any known Poly-APX-complete minimimization problem?

All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
1
vote
2answers
127 views

Is Asymptotic PTAS $\subseteq$ APX?

The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows: A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an ...
2
votes
0answers
44 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
97 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
154 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 ...
3
votes
0answers
56 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 ...
3
votes
1answer
162 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) ...
0
votes
1answer
635 views

Is the current best approximation ratio for Vertex Cover problem also a lower bound?

In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we ...
2
votes
0answers
55 views

General hardness results for convex problems

What are the hardness results that we know of for generally convex problems? In particular, I know of the result that every convex problem is in $P$ when we have an oracle for generating a separating ...
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
1answer
93 views

From Lasserre maps to pseudo-distributions

Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
7
votes
1answer
149 views

What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...
9
votes
2answers
249 views

When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
-1
votes
1answer
114 views

Given oracle for Max-3SAT compute clauses that cannot be satisfied

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
-2
votes
1answer
90 views

Proving hardness of approximation with reduction in terms of 1/$\epsilon$

I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
1
vote
0answers
50 views

About increasing the objective values of certificates for Max-Clique SDP

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
7
votes
1answer
215 views

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3). ...
9
votes
0answers
154 views

NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
1
vote
0answers
90 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$...
0
votes
0answers
59 views

About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
4
votes
2answers
150 views

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

Problem: Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
5
votes
1answer
629 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 ...
5
votes
0answers
241 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 ...
3
votes
1answer
243 views

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 ...
0
votes
0answers
33 views

On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
4
votes
2answers
343 views

Graph coloring/partitioning problem

I'm interested in the complexity of the following problem: Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, ...
15
votes
1answer
334 views

smallest circuit size using XOR gates

Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables. The goal is to compute the minimum ...
1
vote
0answers
103 views

hardness of approximating clique: how using FGLSS reduction with PCP verifier of hastad

I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps In fact, I only want to understand the proof of ...
3
votes
0answers
96 views

Set cover approximation ratio as a function of m (number of sets)

Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an ...
1
vote
1answer
177 views

Is there any research on approximation of reals with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
2
votes
0answers
91 views

Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least 6....
1
vote
1answer
384 views

What are multiple rounds of SOS/Lasserre hierarchy?

Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? Or to take a ...
1
vote
1answer
402 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
3
votes
1answer
367 views

What is a “level-r pseudo expectation functional”?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
5
votes
0answers
215 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
1answer
193 views

Set cover in which some pairs of sets are forbidden

I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an ...
3
votes
0answers
103 views

$\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems

All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ ...