Unanswered Questions
80 questions with no upvoted or accepted answers
16
votes
0
answers
495
views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
- 6,795
13
votes
0
answers
530
views
Approximating and bounding Ramsey numbers
Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer:
Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and ...
CommunityBot
- 1
11
votes
0
answers
240
views
Inapproximability of multiterminal cut
In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
CommunityBot
- 1
10
votes
0
answers
365
views
Gap hardness of Multi-Dimensional Cover
Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
CommunityBot
- 1
9
votes
0
answers
264
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 ...
- 546
8
votes
0
answers
235
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 ...
- 14.5k
8
votes
0
answers
179
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 ...
- 21.8k
8
votes
0
answers
1k
views
Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?
This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal ...
CommunityBot
- 1
7
votes
0
answers
349
views
Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?
In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of ...
- 2,291
7
votes
0
answers
877
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 ...
CommunityBot
- 1
7
votes
0
answers
705
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 ...
CommunityBot
- 1
7
votes
0
answers
548
views
Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?
optimization problem
Input: a 3-connected cubic planar graph
feasible solution: A simple path
measure to optimize: length of the simple path
Is there a constant approximation algorithm for this ...
CommunityBot
- 1
7
votes
0
answers
274
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 ...
- 343
6
votes
0
answers
282
views
Is monotone 1-in-3 MAXSAT known to be APX hard?
Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
- 1,187
6
votes
0
answers
196
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
$$\...
- 271