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.

1,239 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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: ...
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 ...
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. ...
116 views

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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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$?
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 ...
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 ...
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 ...
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 ...
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)&...
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 ...
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 ...
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: ...
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 \...
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 ...
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$...
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 ...
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) = \...
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 ...
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 ...
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 ...
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....
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, \$\...