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

learn more… | top users | synonyms

5
votes
0answers
99 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
-1
votes
0answers
25 views

Suitable weighting algorithm for selection multiple solution

I am doing a mapping system withing two set of key words. So initially I run 3 mapping algorithm which I run on subset of the keywords and get a total of matching. This process is some kind of ...
-1
votes
0answers
79 views

The bounds on the multiplicative weights update method (MWU)

Assume that the costs $m_i^t$ in MWU lie between 0 and 1. The subscript $i$ refers to an 'advising expert' number $i$ and the superscript $t$ refers to time. Let us denote the expected value of the ...
1
vote
0answers
135 views

Dynamic Programming with two optimization goals

I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I ...
1
vote
0answers
103 views

exact cover set problem

i am searching an heuristic algorithm for a weighted exact cover problem shown here: http://en.wikipedia.org/wiki/Exact_cover On my research i only found algorithm which calculates all solutions ...
8
votes
1answer
204 views

Fast algorithm for weighted bipartite matching problem

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks. I have an ...
7
votes
0answers
88 views

Computing the most likely winner in elections : intermediate case between Kemeny and Borda?

Given $n$ possible alternatives satisfying some unknown linear ordering, a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$: $M_{i,j}$ counts the number of votes for which ...
0
votes
0answers
36 views

LP solver for sparse, PSD and strictly diagonally dominant matrix

I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for ...
6
votes
0answers
190 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
1
vote
0answers
108 views

Automatically Adapting Forgetting Factor for Online EM

I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning ...
2
votes
0answers
46 views

Linear ordering of bipartite tournament graphs

I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament ...
1
vote
0answers
68 views

Proof of convergence of alternative minimization/maximization [duplicate]

Given a problem \begin{equation} \max_{x\in X} \min_{y \in Y} f(x,y) \end{equation} where $f$ is strongly convex in $Y$ and strongly concave in $X$ How to show that the following iterative ...
3
votes
2answers
152 views

Iteratively minimizing the function

Consider the problem \begin{equation} \min_{x\in X, y \in Y} f(x,y) \end{equation} Can I solve the problem by iteratively solving the following two sub problems? \begin{equation} x_{k+1} = ...
0
votes
0answers
31 views

arithmetic formula simplication

Consider a function $f : \mathbb R^m \rightarrow \mathbb R^n$. Function $f$ can be written down as a simple arithmetic program. It uses addition, subtraction, multiplication and division - however, ...
4
votes
3answers
367 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
7
votes
3answers
177 views

Job scheduling: minimizing number of reads

Consider the following scheduling problem: input: set of computations $C = \{c_1, ..., c_n\}$ set of computing nodes $P = \{p_1, ..., p_n\}$ Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ ...
0
votes
0answers
62 views

Are there any approaches to the following scheduling problem?

Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters: The time it takes to be completed ($t_i$) and, The ...
0
votes
0answers
61 views

Problems solved by the greedy algorithm for matroids

Given a matroid $\mathcal{M} = (E, \mathcal{I})$ with weights $w : E \rightarrow Q^+$, it is well known that the greedy algorithm finds a maximum weight independent set $S \in \mathcal{I}$ in ...
1
vote
0answers
54 views

Gilmore-Lawler bound for the QAP

I'm stuck with trying to implement the Gilmore-Lawler bound procedure for the quadratic assignment problem (QAP). That is, a bound one can use with a branch and bound algorithm to solve the QAP. I'm ...
2
votes
1answer
80 views

Existing benchmarks for scheduling problems?

Which benchmarks exist to evaluate the performance of algorithms for Job-Shop or Flow-shop scheduling problems?
1
vote
0answers
72 views

NP-hardness of a bilinear program?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$. I have the following bilinear program: max $\sum_{i=1}^n (x_i-a_i)y_i$ ...
5
votes
0answers
114 views

Is there a programming language where any arbitrary recursive function can be fused?

Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
3
votes
0answers
109 views

Generating quadratic optimization problems amenable to quantum annealing

Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
1
vote
0answers
83 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
70 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 ...
2
votes
1answer
75 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
101 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
91 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
134 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 ...
3
votes
0answers
161 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
114 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
153 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
80 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
125 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
129 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
40 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
57 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
155 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 ...
22
votes
3answers
643 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
179 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 ...
6
votes
0answers
110 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
79 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
55 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
36 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
111 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
230 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
139 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
125 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
70 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
227 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 ...