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
2
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
2answers
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$ ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
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
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 ...
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
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)&...
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
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 ...
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
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 \...
2
votes
1answer
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 ...
4
votes
1answer
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$...
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
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) = \...
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
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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....
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
184 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 ...
2
votes
0answers
153 views

How to setup a model for a guillotine cutting stock problem?

Backgroud. I'm reading papers about cutting stock problem (CSP). Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008) Characterization and modelling of guillotine constraints. European ...
2
votes
1answer
59 views

Choosing $n$ points to get the closest sum

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, ...
2
votes
0answers
29 views

Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost: where: ...
2
votes
2answers
153 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
2
votes
0answers
152 views

What is an efficient algorithm to solve the following combinatorial optimization problem?

I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes: weight, shape (denoted by number of faces, $n_{\rm ...
2
votes
1answer
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 ...
2
votes
1answer
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. ...
1
vote
1answer
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 ...
3
votes
4answers
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? ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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). ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 (...
4
votes
3answers
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 | |------...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
3answers
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. ...
-1
votes
1answer
60 views

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

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 ...
2
votes
2answers
173 views

How can I partition a graph such that as few edges as possible cross partition boundaries?

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$ ...