# Questions tagged [optimization]

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

348 questions
Filter by
Sorted by
Tagged with
58 views

### Sum From A List Of Numbers (Algorithm)

I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it... You have a list of numbers and a ...
169 views

### Run Length eXtreme encoded length

In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times. Consider the following "improvement" of ...
388 views

The famous FTPL algorithm  is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of  it says "It would be great to ...
37 views

### Maximization under constraints

I have a set of $m$ sets, each one has $n$ different items. I have a function $f: 2^n \to \mathbb{R}$. ($f$ could be submodular if it helps). I am trying to maximize the function $f$ under the ...
19 views

19 views

### The set of weight functions for which the assignment problem has non-trivial solutions

The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs): $$V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij},$$ where $\cal P$ is a ...
54 views

112 views

### Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$A x = b$$ and the goal is to find a solution $x$ with as few nonzero variables as ...
97 views

### Optimal evaluation of polynomials / rational functions

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
32 views

### Pass ordering for greedy local search algorithms

Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for. I have a problem with the following setup: I have a (finite) totally ...
129 views

44 views

### Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
124 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 ...
72 views

### Linear optimization over intersection of totally unimodular matrices

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...
146 views

### Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
681 views

### Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
221 views

### Optimal partition according to partition cardinality

Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$. We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements. Can ...
78 views

### Reference request — minimizing a non-increasing submodular function with (upper bound) cardinality constraint

Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$. I am wondering if there are ...
389 views

### Optimal value of a semidefinite program

Is a local optimum value of a SDP always the global one? If not, what are the conditions for that?
607 views

### Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
112 views

52 views

### About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?