# Tagged Questions

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

347 views

### Objective function for stochastic optimization

Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
785 views

### Optimization problems with good characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
317 views

### Neural Networks: what's the point of learning features that don't linearly separate?

Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input. In such cases, the input set is linearly inseparable, so the optimisation problem that ...
122 views

### Lower bound for the maximal vectors problem

I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
90 views

### Minimize the time when guard observes more than one event (for fixed number of guards)

Consider the following optimization problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which ...
58 views

### Sync time between two points

Suppose we have two points, A and B, each point has its own clock. We are able to send messages between ...
50 views

### How hard is it to compute an approximately optimal non-greedy CART tree?

The question itself is closer to the bottom of this post, and is formulated without any rerefence to the term "CART". Motivation: In traditional CART (Classification and Regression Trees), one ...
174 views

### Permutation optimization problem

Here is the problem as posed by Jerrum: "The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target ...
316 views

### finding “hubs” in a graph

consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ ...