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

learn more… | top users | synonyms

1
vote
0answers
59 views

Optimization as LP on the convex hull of its solution space

I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem ...
2
votes
0answers
57 views

Is it possible to formalize the notion of 'semi-greediness'?

It is commonly accepted that matroids provide an abstract setting for which greedy optimization works (although there are more general structures known as 'greedoids'). I was wondering whether there ...
1
vote
1answer
29 views

On the stopping criterion of coordinate descent method

I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion. Consider the optimization problem \begin{equation} \min ...
0
votes
0answers
82 views

Help with a special case for Hungarian algorithm

I am working on a problem and it appears to be a special case of Hungarian algorithm. In Hungarian algorithm for assignment problem, there are n people and n jobs. Each person can do any of n jobs ...
-3
votes
0answers
51 views

Self adaptive crossover and mutation for multi-objective Genetic algorithm optimization

I am solving a multi-objective optimization problem where I have many objectives that need to be maximized and minimized. It is similar to bin packing or the knapsacks problem which described in ...
3
votes
0answers
87 views

NP algorithm for an optimization problem

Consider the following optimization problem INSTANCE: vectors $\vec{a}, \vec{b}, \vec{c}$, matrices $A, B$, threshold $\theta$. PROBLEM: Let $f={\displaystyle \max_{\vec{x}, \vec{y}}} ...
0
votes
0answers
128 views

A* in triangulated search space

I have a question regarding the optimality of a specific A* in triangulated search spaces (planar). Suppose I have some convex polygon (the boundary) with some number of obstacles (other convex ...
-2
votes
0answers
58 views

Dynamic programming - variant of knapsack problem

Thank you in advance: I have the following variant of knapsack problem: We have a knapsack of capacity $W$, and a set of $n$ items $I=\{a_1,...,a_n\}$ where each item $a_i$ has a profit $p(a_i)$ and ...
3
votes
0answers
106 views

Computing the convex hull of several polyhedra

Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities. How easy is it to compute an ...
4
votes
1answer
86 views

Gradient descent-like optimization on a convex landscape with noisy sampling

We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$. The goal is to approximate the minimum. E.g. $$f: [0,\pi]^2 \to \mathbb{R}$$ $$f(\theta,\phi) = t_1 \sin \theta + t_2 ...
9
votes
1answer
144 views

Program Minimization

Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs? In particular my question is - Do there exist algorithms to minimize the ...
2
votes
0answers
69 views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
4
votes
1answer
119 views

Is it possible to create an algorithm-aware optimizer?

I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm: ...
2
votes
1answer
120 views

Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

I've given an optimization problem for which I want to show that it is solvable in polynomial time. Now, I have two questions: Can this be done by formulating a mixed-integer linear program such ...
3
votes
0answers
35 views

Optimization of class schedule

I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal. I have n groups, all of which need to do some activity a in time slot t. A person can ...
3
votes
1answer
49 views

Compiler Optimization: How do you automatically fuse conditionals into the loop index?

Let's say that you have some loop for(i=0;i<n;i++){ if(i > 3 && i < 8){ p(i); } } How would I go about automatically fusing that into ...
3
votes
1answer
89 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 ...
21
votes
3answers
591 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 ...
6
votes
3answers
152 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 ...
5
votes
0answers
99 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, ...
3
votes
0answers
68 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 ...
1
vote
0answers
52 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 ...
2
votes
0answers
32 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 ...
5
votes
0answers
82 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 ...
1
vote
1answer
195 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$ ...
3
votes
0answers
113 views

Subset of a bipartite graph with maximal number of minimal unmatched vertices

Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all ...
0
votes
0answers
86 views

dynamic algorithms for the subset-sum problem hold for vectors?

I have a vector (er, array) that is the sum of a number of other known vectors. I would like to reverse the process and find the specific known vectors that were summed to make the final vector. The ...
2
votes
0answers
63 views

KKT-like conditions for values close to optimal solution

The KKT conditions are necessary and sufficient conditions for problems where we maximize over a convex function subject to linear inequality and equality constraints. That is $x^*$ is an optimal ...
2
votes
1answer
195 views

Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?

If this is known, can someone point me to a proof? Edit: A QP is essentially a LP with a quadratic objective. That is, it looks like: minimize $\frac{1}{2} x^T Q x + c^T x$ s.t. $Ax \leq b$ It's ...
1
vote
0answers
72 views

Tiling a rectangle with weighted cells (min-max problem)

Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by ...
-5
votes
1answer
198 views

Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...
3
votes
1answer
67 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
1
vote
0answers
24 views

Nonlinear optimization using parallel input/output

I have a system that accepts a vector and returns a function value. The goal is to change the elements of the vector such that the function value is minimized using a derivative-free solver, eg. using ...
3
votes
0answers
66 views

Symmetry of optimal solutions to discrete optimization problems

Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ...
10
votes
2answers
339 views

Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct). Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} ...
2
votes
0answers
56 views

Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following. Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of ...
-3
votes
1answer
88 views

what problem is this? [closed]

I have this instance: Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ...
-1
votes
1answer
222 views

Program optimization - 90/10 law

I found this "law" somewhere on Wikipedia: In software engineering, it is often a better approximation that 90% of the execution time of a computer program is spent executing 10% of the code ...
5
votes
1answer
95 views

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

Question Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow ...
2
votes
0answers
119 views

Quadratic Binary Optimization formulation of Steiner Tree problem

can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization ...
1
vote
1answer
110 views

Looking for algorithm (or at least name) for this optimization problem

Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$. Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$ The ...
1
vote
0answers
84 views

Why do people like using evolution computing techniques like GA on multi-objective optimisation?

I am new to the field of multi-objective optimisation and I try to find some books to read on this topic. Yet when I search around my library I found there are many books on using evolution computing ...
1
vote
0answers
128 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
3
votes
1answer
122 views

Complexity class for Optimization problems over #P functions

Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e: $$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$ where $f\in\# ...
1
vote
0answers
76 views

Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?

Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so ...
0
votes
0answers
229 views

Formulation of the k-TSP as an integer programming problem?

Specifically, in a complete graph, I'm trying to find the simple path with $k$ nodes that minimizes the sums of their vector edge weights. Additionally, the solution should be Pareto efficient ...
0
votes
0answers
53 views

Continuous version of rod cutting

This is an attempt to extend an idea from Computer Science.. the dynamic programming based solution of the rod cutting problem (given a rod of an integral length and an array of prices for each ...
-1
votes
1answer
103 views

Is l1-norm works better that l2-norm in minimization using projection method?

Given a vector of errors $e(x)$ obtained by variable $x$ In the following problem : $min_x || e(x) ||$ Besides the robustness, consider only convergence speed, is it l1 norm works better than l2 ...
0
votes
1answer
105 views

Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
4
votes
1answer
142 views

Minimize in polynomial time a super-additive increasing function under linear constraints?

I am looking for references whether this problem can be doable in polynomial time (or other known approximation results): Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$), $$ ...