Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

learn more… | top users | synonyms

3
votes
0answers
34 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
1
vote
0answers
13 views

Are pseudo-distributions the same as thing as the linear maps as in the Lasserre hierarchy?

Given polynomials $p,q_1,\dots,q_m$ we consider the optimization question, $\inf \{ p(x) \vert x \in K\}$ for $K = \{x \in \mathbb{R}^n \vert q_i (x) \geq 0, i = 1,..,m\}$ For this case Lasserre ...
0
votes
0answers
25 views

About tensor methods in ML

I am referring to this paradigm as explained here, http://newport.eecs.uci.edu/anandkumar/tensor.html My question is this, do these tensor methods somehow promise to make non-convex optimization ...
0
votes
0answers
13 views

Optimizing the output parameters for a given input

Problem statement: I'm trying to solve a problem statement using C# as programming language. In the problem system for an input (double/decimal) say Hi, the output generated is a form of dataset ...
3
votes
1answer
25 views

About the Max-Cut SDP

The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, ...
4
votes
1answer
62 views

A facility location problem

Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way ...
0
votes
1answer
26 views

Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
4
votes
0answers
76 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
3
votes
2answers
111 views

Solving/Optimizing a linear system in a finite field (Z/2Z)

I'm trying to solve the following optimization problem. A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y ...
1
vote
1answer
27 views

Travelling plan between two places

There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$. At each step $i$ there are two choices: stay where you are or ...
0
votes
1answer
51 views

What is wrong with my LP exercise (longest path cost for a graph)

I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have ...
3
votes
1answer
69 views

Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm". The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the ...
5
votes
1answer
84 views

Finding a certain prefix of a string

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a ...
4
votes
0answers
33 views

job scheduling with deadline and two cascaded machines

Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing ...
1
vote
2answers
51 views

How to optimize a function by maximizing 1 variable and minimizing another?

Problem I want to implement an optimization algorithm for my file transfer program. The program buffers data in a local file before uploading to central server periodically and it compresses the ...
1
vote
0answers
91 views

Finding optimal element with two criteria

Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a ...
3
votes
1answer
111 views

Find a maximum sum in matrix, subject to special constraint

I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in ...
3
votes
1answer
30 views

How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? Here ...
3
votes
2answers
76 views

Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

The protocol is defined here, but I'll give a summary here. Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, ...
2
votes
1answer
30 views

Why cant we round results of linear programming to get integer programming?

Say if linear programming suggests that we need 2.5 trucks to deliver goods why cant we round up and say 3 trucks are needed. Similarly, if linear programming suggests we can afford only 3.7 workers ...
1
vote
1answer
69 views

Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$. I would like to select a ...
5
votes
1answer
94 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
3
votes
1answer
38 views

Remove contiguous subsequence so the remaining numbers will created a sorted sequence

You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then ...
1
vote
0answers
69 views

Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
0
votes
1answer
45 views

Search a preprocessed text with online queries

We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we ...
3
votes
1answer
20 views

Classifier optimization

Suppose we have a set E of entities. Each entity is described by a set P of binary properties (i.e. each element e of E has a defined true/false value for each element p of P). |P| >> |E| We now ...
2
votes
1answer
80 views

Distribute numbers 1,N on a grid as evenly as possible

I'm working on a complex engineering problem that I've essentially reduced to this problem: I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map ...
2
votes
0answers
26 views

Constraint solving for scheduling code with complex unspillable register classes?

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
3
votes
1answer
33 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
8
votes
1answer
141 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
1
vote
2answers
52 views

How to solve an optimization problem that deals with the optimal combination of given ratios?

I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem: So they're a daycare, and they get paid by the ...
0
votes
1answer
38 views

maximum distance in between points in taxicab metrics - inserting and deleting points

Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as $$|x_2-x_1| + |y_2-y_1|$$ Initially, there are given empty set of points. I think how to find maximum ...
3
votes
1answer
69 views

How to use convex hull for this problem

Problem: You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i t$ litres of red and $b_i t$ litres of blue liquid. $t$ need not ...
2
votes
2answers
114 views

Longest cycle in a digraph

Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem? Do we know its ...
3
votes
1answer
58 views

Mathematical optimization with thresholded optimization function

Gradient descent can be used to minimize an objective function $\Phi:\mathbb{R}^d \to \mathbb{R}$, if we know how to evaluate $\Phi$ on any input of our choice. However, my situation is a little ...
3
votes
1answer
103 views

Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$

You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$ and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$ Find the longest ...
1
vote
0answers
2 views

Literature on nonlinear dictionary learning

Can anyone direct me to some literature on learning nonlinear dictionaries? I don't mean sparse dictionaries specifically, but for example learning kernel parameters, or learning $W$ where $y = ...
1
vote
2answers
32 views

What is monograph and digraph in keyboard optimization problem?

I have been working on Bangla keyboard optimization. I've taken this paper as a reference. In this paper they have introduce two terms monograph and digraph. But it is not clear how they have ...
1
vote
1answer
55 views

Scheduling distributed computational graph

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete. The common way to improve simulation performance is to use a suitable distributed linear ...
-2
votes
1answer
65 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
6
votes
1answer
63 views

Bipartite Graph - How to determine largest subsets that are all connected

I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges. I'm looking for subsets $U' \subseteq U$ ...
2
votes
1answer
71 views

Deleting useless (dead) states from a finite automaton

A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the ...
0
votes
0answers
13 views

constant step-size assumption in non-asymptotic analysis of stochastic gradient descent

I have come across some non-asymptotic analysis of stochastic gradient descent algorithm (works of FRancis Bach https://hal.archives-ouvertes.fr/file/index/docid/831977/filename/newsto_hal.pdf) most ...
0
votes
1answer
58 views

Coin Change Problem(Greedy Algorithm)

In Coin Change Problem, If the ratio of Coin Value(Coin(i+1)/coin(i)) is always increasing then we can use Greedy Algorithm? Example- 1,3,4 are denominations of coin. If I want to pay Rs.6 then the ...
4
votes
0answers
47 views

Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$

(At the very bottom of this, I will shortly describe the motivation for this question.) Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ ...
1
vote
0answers
55 views

Integer programming for the courier (goods delivery) scheduling problem

Model: Consider an undirected, weighted, complete graph $G = (V, E = V \times V, w: E \to \mathbb{N}^{+}, r: V \to \mathbb{N}^{+}, d: V \to \mathbb{N}^{+})$. $s \in V$ is a source vertex. $G$ ...
3
votes
0answers
30 views

Enumerate all minimum feedback arc sets

I am looking for (practically) efficient algorithms to enumerate all minimum feedback arc sets of a directed graph. What algorithms should I look at, with practical implementations in mind? ...
3
votes
0answers
48 views

Given an antisymmetric matrix, how do I find a set of rows that maximizes function?

Let $P$ be an $m \times m$ antisymmetric matrix of the form: $$ \begin{bmatrix} 0 & p_{1,2} & ... & p_{1,m} \\ -p_{1,2} & 0 & ... & p_{2,m} \\ \vdots & \vdots & \ddots ...
3
votes
1answer
96 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
0
votes
1answer
21 views

Optimized resource allocation problem

I am from ECE background and trying to solve channel allocation problem. Let's assume I have three users and three available channels. I would like to allocate channel among them in such a way that ...