# Questions tagged [optimization]

general questions about selecting a best element from some set of available alternatives.

134 questions
296 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 ...
202 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 ...
189 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?...
197 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. ...
103 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 ...
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 ...
109 views

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&... 0answers 686 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 ... 0answers 152 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 ... 0answers 106 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$$... 0answers 143 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 ... 0answers 214 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 ... 0answers 142 views ### Lower bound for the maximal vectors problem I am studying the (worst-case) complexity$C(n,d)$required to solve the maximal vector problem: given a finite set$V$of$nd$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ... 0answers 367 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 ... 0answers 456 views ### Which problems in graph theory can be stated as quadratic programs? There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency${\bf A}$or the Laplacian matrix${\...
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 ...