Unanswered Questions
183 questions with no upvoted or accepted answers
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
12
votes
0
answers
286
views
the largest element of a matrix product
Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?...
- 259
12
votes
0
answers
308
views
Expected length of a self-avoiding random walk
We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
...
- 531
10
votes
0
answers
245
views
Complexity of cycle cancellation with integral capacities and irrational costs
Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along ...
- 23.3k
9
votes
0
answers
306
views
Shortest string in the intersection of regular languages
Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string
Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
8
votes
0
answers
152
views
What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)
Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$.
The Entropy-Constrained Quantization problem asks what is the best ...
- 9,508
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
114
views
Computing the most likely winner in elections : intermediate case between Kemeny and Borda?
Given
$n$ possible alternatives satisfying some unknown linear ordering,
a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$:
$M_{i,j}$ counts the number of votes for which $i&...
- 1,095
8
votes
0
answers
416
views
Permutation optimization problem
Here is the problem as posed by Jerrum:
"The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target ...
- 11.6k
8
votes
0
answers
366
views
View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?
Also called exponentiated gradient.
I understand these are three places where multiplicative weights shows up (i.e. $w_{t+1} = w_{t}e^{- \text{loss}(w_{t})}$ or variations. And I understand a bit ...
- 10.3k
8
votes
0
answers
820
views
Is this minimization problem NP-Complete?
We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns.
The problem is ...
CommunityBot
- 1
7
votes
0
answers
176
views
A class of functions on a lattice that are easy to optimize
Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
- 201
7
votes
0
answers
121
views
Has compressed sensing been generalized to convex optimization problems?
Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type
$$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$...
- 71
7
votes
0
answers
159
views
SVM - running time for detecting if data is linearly separable?
If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
- 14.1k
7
votes
0
answers
228
views
Is there a programming language where any arbitrary recursive function can be fused?
Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
- 3,217