Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
349
questions
-1
votes
0answers
18 views
Time complexity for Linear Discriminant Analysis Problem
Linear Discriminant Analysis Problem:
Given $n$ points in $\mathbb{R}^d$ which are grouped into two classes, find a linear discriminant (hyper-line) which classifies points such that minimizing mis-...
0
votes
2answers
329 views
Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums
My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
2
votes
1answer
107 views
Sum From A List Of Numbers (Algorithm) [closed]
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 ...
1
vote
0answers
198 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 ...
0
votes
0answers
19 views
Algorithmic gap for greedy algorithm for (metric) uncapacitated facility location
In Jain et. al (2003), at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega(\frac{\...
3
votes
0answers
41 views
AMQ (Bloom-filter like structure) lower bounds
I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the ...
1
vote
1answer
68 views
Embedding a n-tree into a b-dimensional space
Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $...
0
votes
0answers
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 ...
4
votes
1answer
56 views
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \...
-3
votes
1answer
97 views
Finding the maximum no. of people who get along in a group [closed]
Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
0
votes
0answers
28 views
Alternating Delivery Problem
What is known about the complexity of the following problem:
Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...
1
vote
1answer
92 views
Vehicle scheduling
Suppose there are $n$ resources which can do some work. Each resource has a number of time windows: $tw_{i,k}=\{start_{i, k},stop_{i, k}\}$, such that the resource can perform its functions only ...
1
vote
0answers
47 views
Problems rephrased as quadratic unconstrained binary optimization
I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
3
votes
1answer
136 views
Intuitive explanation behind Goemans-Williamson randomized rounding
A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
1
vote
1answer
88 views
3 dimensional matching shortest solution NP-hard?
We have array of arbitrary number of elements - 3d vectors with positive integers components - for example
...
2
votes
1answer
125 views
Generalizations of linear programming
Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.
Is there a survey/lecture notes describing ...
0
votes
2answers
71 views
Bellman-Ford with Non-edge-decomposable Path Weights
Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a ...
1
vote
0answers
124 views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
2
votes
1answer
102 views
Maximum-minimum satisfiability
In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\...
3
votes
2answers
113 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 ...
1
vote
0answers
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 ...
1
vote
0answers
40 views
Back-propagation for computing derivative of certain line integral
Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
1
vote
0answers
35 views
Best approach for allocation problem
I am a bit rusty on optimization algorithms and need an advice. This is my problem:
I have n images (with width and ...
1
vote
1answer
129 views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and ...
2
votes
1answer
99 views
Stochastic gradient methods and risk of neural nets
Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....
2
votes
1answer
102 views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
1answer
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 ...
9
votes
0answers
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 ...
3
votes
0answers
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}&&...
6
votes
0answers
147 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 ...
1
vote
1answer
84 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 ...
1
vote
1answer
123 views
Minimum graph cut with constraints
Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,......
1
vote
0answers
33 views
Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent
I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
1
vote
0answers
55 views
Minimization of the maximal adjacent integer sums on a circle
Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
3
votes
0answers
60 views
Primal/Dual of the Lasserre/ SOS SDP hierarchy
Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was ...
4
votes
1answer
425 views
Minimum Union-Sum Cost Path
I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
1
vote
2answers
84 views
Partitioning a square for optimal queries
I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:
$f(x, y, r)$ tells me how many ...
3
votes
1answer
47 views
Algorithm for finding smallest set and instanciation for a given constraint system
I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:
...
3
votes
0answers
89 views
Showing hardness of maximizing stochastic objective function over graph
Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$.
The challenge is to ...
0
votes
1answer
54 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?
1
vote
0answers
33 views
Getting to local/global minima with (stochastic) gradient descent on non-convex objectives
Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ...
3
votes
1answer
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 ...
1
vote
1answer
179 views
Monotone supermodular function minimization under partition matroid constraints
Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?
2
votes
0answers
168 views
Is Non-linear Constrained Optimal Exact Cover NP-Hard?
Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
0
votes
1answer
40 views
How do minimally violated k-mod cuts work (intuitive explanation)?
As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors....
2
votes
1answer
421 views
Maximum difference between two shortest paths
My problem is the following maximization problem:
Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two ...
3
votes
2answers
288 views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
3
votes
0answers
120 views
Stacks serving interval storage requests
An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
3
votes
0answers
65 views
Minimizing a sum of thresholded quadratics
Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors, and $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of
...
5
votes
0answers
170 views
Which well-known algorithmic problem is this an instance of?
Consider that you have n counters initialised with numbers $M_1 \dots M_n$. In each round you decrement exactly $k$ out of these counters. Keep doing this until at least $n-k+1$ counters are zero, so ...
