Unanswered Questions
210 questions with no upvoted or accepted answers
17
votes
0
answers
788
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 ...
- 5,793
15
votes
0
answers
391
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 ...
CommunityBot
- 1
14
votes
0
answers
633
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 ...
- 21.8k
14
votes
1
answer
344
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 11.1k
12
votes
0
answers
370
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
...
- 6,795
10
votes
0
answers
299
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{...
- 12.4k
9
votes
1
answer
374
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 ...
CommunityBot
- 1
9
votes
0
answers
285
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 $\...
- 323
9
votes
0
answers
309
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,508
8
votes
0
answers
112
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 ...
- 3,450
8
votes
0
answers
233
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
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
367
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 ...
CommunityBot
- 1
8
votes
0
answers
569
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
...
- 725
7
votes
0
answers
104
views
Jump number approximation algorithm
A linear extension $x_1 x_2 \ldots x_n$ of a partially ordered set (poset) is said to have $k$ jumps if there are $k$ occurrences of consecutive elements that are incomparable with each other -- i.e., ...
- 342