# Questions tagged [optimization]

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

1,266 questions
Filter by
Sorted by
Tagged with
37 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 ...
398 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 ...
478 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 ...
176 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$ ...
54 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 ...
351 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$?
74 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 ...
33 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 ...
127 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: ...
297 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 \...
1k 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 ...
97 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 ...
95 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 ...
153 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 ...
70 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 ...
189 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....
31 views

367 views

### Aggregate planning with inventory

I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging. The following is given: 1100 units can be produced each month ...
266 views

### Why does the time/space tradeoff exist

I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff. Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff. ...
192 views

### Verifying if a greedy solution is optimal for a specific instance (Set cover)

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution. Is there an efficient way of verifying if, for that particular instance, the given solution ...
128 views

### Can loops like this one be algorithmically transformed into multiplication

Are there known techniques for converting a loop like the following to an if and a multiplication? ...
1k views

### Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
44 views

### How to prevent moire artifacts in this light casting algorithm?

I am writing a 2D light casting algorithm with OpenGL compute shaders. The algorithm is simple: For each light source shoot out light rays from it, the ray begins at the light coordinates, it ends at ...
328 views

### Scheduling / Queuing jobs with multiple different workers

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system. Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue). ...
70 views

### Data Searching from a large data set without reading each element

I have just started learning algorithms and data structures and I came by an interesting problem. I need some help in solving the problem. There is a data set given to me. Within the data set are ...
65 views

### Is this problem a variant of TSP problem? if not, what is it called?

A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are ...
59 views

### Understanding the geometrical interpretation of word2vec

I'm trying to understand how the $word2vec$ method actually nudges word vectors of similar semantic/syntactic content closer together in the word vector space. I've read here (Quora answer) that it's ...
81 views

### Maximisation of graphs weight

I have a graph related problem. Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total ...
63 views

### Are there many empirical results about which metaheuristics are well-suited for which problem domains?

One of the nice things about genetic algorithms is that they can easily be used for a diverse array of problem domains, whereas PSO for example seems best-suited for candidates of real-valued vectors (...
2k views

### Portfolio rebalancing algorithm

Quite possibly this problem is already solved and has it's own name, but I was unable to find any directions. So, I have a portfolio with some items in it: | Name | Price | Amount | Share | |------...
94 views

### Was the “cuckoo search” independently discovered before 2009? If so, what was the name given to it?

Background: I would like to experiment with evolutionary algorithms to generate the "optimal" poem, according to a fitness function to be determined later. However, I cannot think of a good way of ...
73 views

### Lazy evaluation on slow Boolean functions (optimization)

Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this ...
472 views

### Algorithm to choose the best team of 6 Pokémon given a constraint

Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function. ...
Recall the notion of NPO problem. An NPO problem is simple if the following is true: $\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$ In words, given any positive integer $k$, the ...
The following problem appeared while trying to distribute a program over a cluster of computers: Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ ...