Tagged Questions

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

learn more… | top users | synonyms

3
votes
1answer
64 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing ...
0
votes
1answer
79 views

Finding optimal subset for quadratic function

Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of ...
10
votes
0answers
193 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
5
votes
0answers
111 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
vote
0answers
146 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
111 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
215 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
89 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
39 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
198 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
109 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
47 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
154 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
368 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
65 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
65 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
56 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
96 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
75 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
117 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
111 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
84 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
78 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
107 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
92 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
163 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
124 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
81 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
127 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
58 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
158 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 ...
23
votes
3answers
664 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
186 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
116 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
242 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
162 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
136 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
71 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 ...