Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...