general questions about selecting a best element from some set of available alternatives.
-1
votes
0answers
85 views
How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem? [on hold]
Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set S of size k, if there exists ...
1
vote
1answer
50 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
52 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
23 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
52 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
37 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
275 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
0answers
35 views
maximization of non-negative monotone supermodular set function with cardinality constraints
the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality ...
1
vote
2answers
82 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
42 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:
...
0
votes
0answers
12 views
Modelling a fixed-size chromosome for a variable task number in a genetic algorithm
I'm trying to use GA to solve a fairly simple scheduling problem with a set of agents. Agents are just moving entities that have simple and predictable trajectories. They need to "capture" information ...
4
votes
0answers
78 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
41 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
30 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 ...
0
votes
0answers
44 views
Find the maximum induced (weighted) subgraph with edge weights greater than some minimum
I have a (fully connected) weighted undirected graph.
I want to find a maximal induced subgraph whose edge weights are all above some minimum value.
Or, if not a maximal subgraph, then with some ...
0
votes
0answers
43 views
Problem: Scheduling diverse teams while minimizing frequency
I have the following problem which I have been asked to solve. I like to think that a few years ago, I'd be able to do it myself, but these days I must admit that help is good :)
Given $n$ employees $...
2
votes
0answers
191 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 ...
0
votes
0answers
227 views
Complexity of Quadratic Programming
I'm trying to learn the complexity of a quadratic program in the form of:
minimize:
$f(x,y)=x^2-y^2-4xy$
given only $x*y$
s.t.
$x=a+b$
$y=a-b$
$x+y>3\,\sqrt{xy}$
$x,y,a,b >0$
What I ...
0
votes
1answer
72 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 ?
0
votes
0answers
111 views
Does binary search converge faster than gradient descent on 2 convex functions?
Here is the thing, I have two functions, lets call them $E_0$ and $E_1$. The functions are both convex, and they essentially look something like this:
Now I am looking to get an $\epsilon$ close to ...
2
votes
0answers
154 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
34 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....
0
votes
0answers
58 views
How does an NP-complete continuous optimization problem map to Boolean SAT?
I looking at this paper where the authors mention that the following problem:
"Given a neural network and a set of training examples, does there exist a set of edge weights for the network so that ...
2
votes
1answer
332 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 ...
0
votes
0answers
29 views
Lower bound on the complexity of projection onto simplex?
The projection onto the simplex problem is the following optimization problem:
$\mathbf{x} = \text{argmin } ||\mathbf{x} - \mathbf{y}||_2$
subject to
$\mathbf{x} \geq 0$, $\mathbf{1}^{\text{T}} \...
3
votes
2answers
265 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
116 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
64 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
169 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 ...
4
votes
1answer
416 views
Understanding the No Free Lunch Theorem
I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out
to me. The first was that we can't define a uniform ...
0
votes
0answers
139 views
Data structure to search name of files and get its path
I will be inserting names of files in a dynamically way, approximately till 1 billion of names. Besides, I do also want to store the path where the files are located in order to do the following ...
0
votes
0answers
58 views
Flow Optimization: minimum cost matching of demands from multiple sinks
The Graph
I've been looking into a flow optimization problem (please follow the above link to view the directed acyclic graph with the source and multiple sinks)
We have a single source 1 and ...
1
vote
0answers
80 views
QUBO formulation of a discrete-variable optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
1
vote
1answer
166 views
Common terminology used for lower/upper bounds
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
3
votes
1answer
79 views
Centroid in $\ell_2$ distance
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$
0
votes
0answers
45 views
Wavelet based Non linear optimization technique
I am outlining a method for solving Non Linear optimization problems.
Consider the system of equations:--------------------------------- 1
f1(a0, a1, a2, a3 ......... an) = 0
f2(a0, a1, a2, a3 ........
1
vote
0answers
130 views
Convergence of Q-learning with non-linear function approximation
Q-learning is a well-known algorithm in Reinforcement learning which enjoys great empirical success but with insufficient theoretical understanding. In the tabular setting, it is known that if each ...
7
votes
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 ...
1
vote
1answer
101 views
Solving linear program with 1 quadratic constraint complexity
Consider the following linear program,
$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \...
-1
votes
2answers
118 views
How to continue this algorithm? [closed]
I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º).
I have thought about ...
0
votes
0answers
387 views
What is the difference between NSGA-II and NSGA-III?
Can someone please explain the difference between the two versions of Non-dominated Sorting Genetic Algorithm NSGA-II and NSGA-III?
4
votes
0answers
398 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 ...
1
vote
0answers
41 views
Average case or beyond worse case analysis for non-convex optimization procedures?
I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature.
It is known that global optimization of non-convex functions is NP-...
1
vote
0answers
46 views
Parametrically-relaxed Kolmogorov complexity
Consider the following problem:
Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.
Output: The encoding of some kind of automaton (say, a Turing machine) which ...
4
votes
1answer
532 views
Minimal Cost of Eulerian Path
Problem:
Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
5
votes
1answer
239 views
Modifying Edmonds' Blossom Algorithm
Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...
0
votes
0answers
126 views
Grover's for QUBO form?
My preferred formulation of the quadratic unconstrained binary optimization problem (QUBO) is the following:
Find $\min(z)=x'Qx$, where $x$ is a $n$-vector of binary variables, $x'$ is its transpose, ...
1
vote
1answer
66 views
Finding an answer key given tests and scores
Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete ...
1
vote
0answers
54 views
Polynomial cases of 0 1 quadratic programm with linear constraints
A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where
Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial ...
3
votes
0answers
56 views
Studying the hardness of polynomial-time approximability using the concept of stability of approximation
In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that
Using the notion of stability one can ...
