We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
544 views

How to construct the objective function for genetic algorithm optimization?

I am trying to optimize a coefficients of filter by minimizing sum-squared error. I want to use a genetic algorithm (GA) optimization wherein the coefficients of filter form the GA's chromosome (a ...
1
vote
1answer
388 views

How to classify a 3D “Knapsack” problem where the only limitation is space, i.e. there is no weight constraint?

The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of ...
2
votes
2answers
411 views

Finding the shortest sublist that contains all search terms

I've been trying to get better at writing algorithms and came across a problem that was something like this: Given a list of words: ...
3
votes
1answer
65 views

Buying as many items for as much money

I cant find a way to implement a certain solution. Let me flesh out the problem. Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money ...
1
vote
2answers
262 views

INOI 2017 Problem 2 - Training

INOI 2017, Problem 2, Training Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order. ...
2
votes
0answers
116 views

Find a permutation that maximizes $\sum_i a_{i-1}a_ia_{i+1}$

I want to solve the following problem: You have a list of numbers, for example [10, 33, 7, 7, 12]. The goal is to find the permutation of this list that maximizes the function $\sum_i a_{i-1} ...
1
vote
1answer
35 views

Is graph search of shortest (optimal) path an instance of optimisation?

I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm. I am not too familiar with graphs / trees ...
2
votes
1answer
94 views

black-box function optimization with binary vector input: terminology and NP-hardness proof

I have a black-box function optimization problem: $$\arg\max_{\vec{x}} \; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}_2^N, \|\vec{x}\|_1=K, K<N, \vec{y} \in \mathbb{Z}_2^M$$ ...
0
votes
0answers
162 views

Why is sequential search of ordered list slower than search of unordered one

I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to ...
3
votes
0answers
65 views

Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image ...
1
vote
1answer
70 views

Filling a 3x3 board with connected tiles

long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern ...
3
votes
1answer
102 views

Feedback Vertex Set with vertex partitions?

I've encountered this problem in a program analysis project I'm working on, where I've got a bunch of functions defined in terms of each other, and because I'm using SMT which doesn't support ...
0
votes
1answer
23 views

How to prevent the optimization algorithm from just shrinking the image?

I'm trying to optimize a set of patterns in an image, but unfortunately they only way I have of evaluating the images results in smaller versions of the pattern scoring much better than larger ...
1
vote
1answer
190 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
2
votes
2answers
227 views

Algorithm Question: Stacking bricks of different colours?

I have a bunch of coloured bricks. There are X different colours, and a random number of each colour. How do I stack them up into Y columns so that a) no row has two bricks of the same colour and b) ...
1
vote
2answers
65 views

Element wise product sum of two arrays

I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving ...
7
votes
1answer
266 views

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
1
vote
1answer
126 views

Size of neighborhood in local search for symmetric TSP

I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things. The given example said: Suppose we have an instance of the symmetric TSP ...
1
vote
1answer
385 views

Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my ...
1
vote
0answers
414 views

Exact algorithm for the partition problem

The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple ...
3
votes
1answer
49 views

Maximize the number of satisfied disjunctions

I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas,...
1
vote
1answer
87 views

Firefly algorithm number of objective function calls

Reading an article (arXiv) about the Firefly optimization algorithm, it is stated that the objective function is called only once per firefly per iteration, but following both the pseudo-code in the ...
1
vote
0answers
657 views

Task scheduling algorithm (minimize wait time)

Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once. I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1\le t_2\...
2
votes
0answers
35 views

How many times does a pair of numbers co-occur in a list?

Imagine you have N distinct people and that you have a record of where these people are, exactly M of these records to be exact. For example ...
0
votes
1answer
392 views

How to get the optimized quicksort algorithm's time complexity

I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to ...
1
vote
0answers
458 views

Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
1
vote
2answers
169 views

Longest path among subset of given points

I am looking for an efficient algorithm to solve the following problem: Given $n$ points in 2D Cartesian space $p_1,\dots,p_n \in \mathbb{R}^2$ and an integer $m$, we want to find $s_1,\dots,s_m$ ...
1
vote
1answer
50 views

What algorithm to use for this kind of routing optimization?

Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS ...
0
votes
0answers
332 views

Round-Robin schedule: process A's time quantum expires at the same time as a process B arrives. What happens next?

Let's assume we are to implement a Round-Robin algorithm. What will happen in a case when a process has completed it's time quantum at the same time as another process arrives. Let's say we have a ...
0
votes
1answer
55 views

Paper-based algorithm to find longest formula which is common to at least two formulas

Given a list of logical formulas: f1: A&B f2: A&D&C f3: B&D&E f4: A&B&C f5: fn: ... In this case I want A&B as the longest formula which is common to at least two formulas. Is there a simple ...
1
vote
0answers
65 views

Global Minimum of Multivariate Polynomial is coNP-complete? [closed]

Is the following problem coNP-complete? Inputs: $p=$ a possibly non-convex multivariate polynomial over $\mathbb Z$ $k\in \mathbb Z$, an integer Question: Is $\forall x\in\mathbb Z: p(x)\geq k$?
2
votes
0answers
71 views

How to sum vectors to maximize magnitude? [duplicate]

There are $n$ vectors, represented as $(d_x, d_y)$ pairs. Someone stands at point $(0, 0)$ of infinite euclidean grid. For every vector he can either move by $d_x$ in $x$ axis and $d_y$ in $y$ axis or ...
1
vote
1answer
90 views

I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?

There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable ...
0
votes
0answers
33 views

Algorithm for computing a sum with multiples of specific values

I am attempting to compute a known sum or closest value to that sum using the multiples of a subset of numbers. In this approach I want to minimize the multiples or coefficient. For instance if I ...
1
vote
1answer
75 views

How to convert between bases partially?

I have some large number $n$ in base $b_1$ and I want to convert it to base $b_2$. $n$ is about a million decimal digits long, therefore it's impractical to convert it as a whole. However I don't need ...
0
votes
0answers
32 views

Appropriate optimization algorithm for constraints having NaN values

I am trying to solve a problem where some of the constraints have NaN values. Which algorithm can be used to handle this kind of problem. In my example I have 3 nonlinear inequality constraints, C(1)&...
0
votes
1answer
31 views

What do you call a lower/upper bound that is the best one?

I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it ...
1
vote
1answer
126 views

Greedy algorithm: Minimizing the maximum of a list

Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last ...
1
vote
1answer
1k views

How one epoch completes in Perceptron?

I am confusing on completing one epoch, I am using Single Layer Feed Forward neural Network approach. Lets suppose i have a data of OR Gate: ...
2
votes
3answers
290 views

Modification of dynamic programming for a knapsack problem

We have the following recursive function for the dynamic programming problem for a knapsack problem: \begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
2
votes
1answer
993 views

How to count all contiguous subsequences with positive sum?

I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$. I need to count how many contiguous subsequences have positive sum. This pseudocode demonstrates ...
4
votes
1answer
89 views

Finding a minimum of a noisy function

I have a certain function that calculates numerically, for every $x \in [0,10]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$...
0
votes
1answer
32 views

Distibutional problem

Given: $n$ tasks with accomplishment times $t_1, t_2, \ldots , t_n$. There is no such task that its accomplishment time is greater than the overall accomplishment time of other tasks. Question: How ...
2
votes
0answers
94 views

Efficient algorithm for “group-sum-min” problem

Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define $$ S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \} $$ and $$ f(s) = \...
2
votes
2answers
69 views

Optimal Partition of Book Chapters

Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions: by the end of each day, you ...
1
vote
3answers
147 views

Solving a discrete optimization problem

Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative ...
3
votes
1answer
67 views

affinity based static load balancing

I am trying to find a good model the following problem: Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
3
votes
1answer
185 views

Is this problem just an application of traveling salesman? If not is it some other already “solved” problem?

Description of the problem in question: Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices....
1
vote
1answer
31 views

What kind of optimization problem this belongs to?

Supervised learning is: given $X$ and $Y$, we want to find a good predictive function $f$ such that $f(X)$ is "close" to $Y$. Examples include XGBoost (ensemble of decision trees), neural networks, $\...
0
votes
1answer
170 views

Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...