Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
369
questions
-2
votes
1answer
53 views
Hardness of maximizing difference of functions [closed]
Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP-HARD but maximizing $f-g$, with $g$ being another function over $D$, is easy (in PTIME). What can be said ...
5
votes
0answers
84 views
Exact algorithms for $k$-means
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
0
votes
0answers
80 views
Algorithms and approximations for optimal offline binary tree operations
Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
1
vote
0answers
34 views
Additive welfare maximization under matroid constraints
In the welfare maximization problem, there is a set $[m]$ of items, and $n$ functions $w_i: 2^{[m]} \to \mathbb{Z}_+$. The goal is to partition the items into $n$ subsets $S_1,\ldots,S_n$ such that ...
2
votes
1answer
90 views
Compiling einstein sums optimally
Einstein summation is a convenient way to express tensor operations which has found its way in tensor libraries like numpy, torch, tensorflow, etc.
Its flexibility lets us represent the product of ...
1
vote
0answers
27 views
Minimum graph cycle basis respect to non-empty pairwise intersection of cycles
I'm trying to understand the following problem if anyone can help I'll be very grateful
Instance: undirected, unweighted, connected graph graph $G=(V,E)$.
Question: find a minimum cycle basis $B = \{...
0
votes
0answers
105 views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...
1
vote
2answers
100 views
Where to find info on (polytime) approximability of various discrete optimization problems?
Where to find info on (polytime) approximability of various discrete optimization problems?
Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
3
votes
1answer
101 views
Parametrized complexity of sparse optimization
Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
4
votes
0answers
83 views
Complexity of finding the mean of the subset with smallest variance
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer.
Let's consider the following problem
$\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\...
9
votes
1answer
335 views
Is the following graph optimization problem approximable within a constant factor?
Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
1
vote
1answer
85 views
Name of (and solution to) this generalization of linear assignment
I would like to know if the following problem is known and has any efficient solution.
Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no ...
0
votes
0answers
38 views
Would a machine learning algorithm benefit from an “optimization oracle”?
I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard.
Now let'...
-1
votes
1answer
59 views
Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]
Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
1
vote
0answers
24 views
Are the intermediary sets in maximum cardinality search optimal in some way?
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
0
votes
1answer
82 views
Finding the size $k$ subset in a metric space that maximizes the min distance between elements
I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements.
We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, ...
5
votes
0answers
82 views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
1
vote
0answers
48 views
Tight estimates on the Lovász and Multilinear extensions of a submodular function
I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear).
Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For ...
2
votes
0answers
30 views
Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
0
votes
0answers
87 views
NP-Hard Knapsack Instances
Consider the classic Knapsack optimization problem (KP):
Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
3
votes
0answers
52 views
Gradient descent step size for strongly convex functions
Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \...
0
votes
0answers
60 views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
0
votes
1answer
77 views
Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?
$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity
$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$
of some string of symbols $x \in \...
0
votes
1answer
107 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
0
votes
2answers
446 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
139 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 ...
2
votes
0answers
208 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 ...
3
votes
0answers
49 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
2answers
100 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 $...
4
votes
1answer
61 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
113 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 ...
1
vote
1answer
100 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
84 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
158 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
120 views
3 dimensional matching shortest solution NP-hard?
We have array of arbitrary number of elements - 3d vectors with positive integers components - for example
...
4
votes
1answer
148 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
92 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
125 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
116 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
133 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
64 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
37 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
134 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
103 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
108 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
48 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
174 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
82 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
158 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 ...
