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

0
votes
0answers
19 views

Multivariate optimisation data-structure / algorithm?

Based on constraints given at runtime, is there an efficient way of finding the answer? Given $n$ rows with $k$ columns. To exemplify, with $n=3$ and $k=3$: ...
2
votes
1answer
18 views

Monotone Frameworks: Transfer functions for flow edges instead of labels

So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$. The goal ...
2
votes
0answers
27 views

A fast algorithm for a simple multi-objective minimization?

I have a set $S$ of $n$ (arbitrary) integers which I want to partition into subsets $S_1, \dots, S_k$, each of size $n/k$ (you can assume that $k$ divides $n$). Let $A$ be the arithmetic mean of ...
6
votes
1answer
48 views

Mathematical optimization on a noisy function

Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x ...
3
votes
1answer
45 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
5
votes
0answers
52 views

Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace ...
0
votes
0answers
13 views

What do we schedule in JSSP? [duplicate]

I am working (for my personal knowledge) on the Job Shop Scheduling Problem, after doing some research on this topic, I still cannot figure out what do we schedule ? Do we schedule jobs or do we ...
5
votes
1answer
109 views

Fast solution for a combinatorial maximizaton problem

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 ...
-1
votes
1answer
16 views

Scalar by N component vector multiplication faster than O(N)?

Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar? It feels to me that there should be some exploit to do that. After all we will ...
1
vote
1answer
28 views

Integer Programming - packing wolves and sheep

I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and ...
0
votes
1answer
24 views

What is the advantage of Day-Stout-Warren algorithm for balancing BST?

While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time. In my opinion I can ...
1
vote
0answers
17 views

C++: Minimization Using Levenberg Marquardt to Solve for Two Variables [closed]

I am trying to solve this equation using C++: X and Y are both given sets of data. X = [x1, x2, ... , xn], Y = [y1, y2, ... , yn] a is a given integer. The goal is to find a pair z and k that ...
3
votes
1answer
25 views

Finding set of disjoint sets with additional value optimization

I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties: Sum of all $v$'s is ...
1
vote
0answers
8 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
3
votes
1answer
35 views

How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves ...
9
votes
2answers
108 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
1
vote
2answers
28 views

Litterature on network-flow (optimization) approximation algorithms

I've been searching on litterature about approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree. However, been looking in several well-known ...
2
votes
1answer
35 views

Spandex knapsack?

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
2
votes
0answers
29 views

Optimize sequence when item costs are interdependent

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there. ...
2
votes
1answer
48 views

Optimal wagering to minimize expected time to reach a target payoff

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
1
vote
1answer
59 views

Are there some real-world optimization problems with very cheap objective functions?

Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a ...
1
vote
1answer
98 views

Find a quarrel-free seating order with a greedy algorithm [duplicate]

I'm revising for an Algorithms exam and looking at a sample question it says : A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy ...
1
vote
1answer
17 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
6
votes
1answer
96 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
5
votes
3answers
202 views

How to choose the maximum number of nodes (with constraints) from a graph

Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. A positive integer $x$ is given and you want to choose at ...
15
votes
3answers
250 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
0
votes
2answers
74 views

Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
0
votes
2answers
50 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function ...
2
votes
1answer
40 views

How should I choose the neighborhood structure for simulated annealing for my problem?

There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C_i \subseteq \{1,\ldots,m\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a ...
0
votes
0answers
15 views

Prove a characterisation of the minimum directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
3
votes
1answer
84 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
1
vote
0answers
56 views

Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
3
votes
2answers
50 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
1
vote
1answer
97 views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
0
votes
0answers
35 views

How can I solve this constrained assignment problem?

The assignment problem is defined as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on ...
1
vote
1answer
65 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
1answer
64 views

The most efficient way of finding/storing neighbourhood info during octree creation

Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box ...
1
vote
1answer
30 views

Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...
1
vote
0answers
25 views

Separate points inside set

I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ...
1
vote
1answer
27 views

Why would this Semidefinite Program be Dual Infeasible?

My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is ...
2
votes
1answer
40 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
5
votes
1answer
370 views

What is the formal name for this algorithmic problem?

I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction. The problem is ...
3
votes
1answer
49 views

What is the Certificate for Set Cover?

Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, ...
2
votes
1answer
216 views

Is Differential Evolution a genetic algorithm?

I am trying to classify the Differential Evolution algorithm according to the framework in the book: Introduction to Evolutionary Computing The authors classify the field of evolutionary ...
2
votes
1answer
50 views

Is ecological bin packing NP-hard?

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as: Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, ...
0
votes
0answers
15 views

Is current hardware adequate for neural networks ? Are there more adequate hardware?

If you have a large neural network and you use more than 10 cores, it will be limited by the fact each core will need to read/write data that it can't access fast enough. I've read about some samsung ...
4
votes
1answer
165 views

Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
3
votes
1answer
40 views

What algorithm is suitable for very small scale, time dependent optimization?

I have a time-dependent (dynamic) optimization problem: $$ f_t : [0;1]^2 \mapsto \mathbb{R}^+; t \in [1, \dots, n] $$ $f_t$ is to be maximized. That is for each $t$ I would like to find a relatively ...
1
vote
0answers
14 views

State of art quadratic knacksack algorithms

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
-1
votes
1answer
100 views

how to improve solution generated by greedy method for 0-1 knapsack? [closed]

I am working on 0-1 knapsack using greedy method, I have some problem in it. It's already proved that solution generated by greedy method for 0-1 knapsack is may or may not be optimal. If solution ...