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
6answers
792 views

Why are all these full-fledged workstations running massive OSes with massive software required all over the world?

I've grown up with computers. I use them every single day, all day. I'm old enough (mid-30s) to have experienced a lot of interactions with "the general public". In particular in later years, I have ...
1
vote
0answers
27 views

Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
0
votes
1answer
31 views

Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;
4
votes
0answers
27 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
0
votes
1answer
19 views

How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

So here's the problem: -You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid ...
3
votes
1answer
57 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
1
vote
1answer
21 views

What's the correct algorithm to filter accumulating string concatenations?

I have a function that is receiving messages with the following pattern: (In this picture, "string" and "message" are synonymous.) I'm only interested in the largest messages, such as these: over a ...
0
votes
1answer
25 views

What happens with register usage in deeply nested functions calls (in theory)?

I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, ...
0
votes
0answers
6 views

Efficiently populate a look-up table for a function over a range of arguments

I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value. I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its ...
0
votes
0answers
16 views

Optimization problem (maximize output)

Problem I have an optimization problem, where I want to find the value of parameters X1, X2 ... Xn which will give the highest output Y. Variables Several X variables are dependant. For example, ...
0
votes
0answers
15 views

What does the gradient mean in evolutionary algorithm?

I have been reading about evolutionary algorithms and I often find the concept of gradient that is used as "to follow a gradient"...
1
vote
0answers
21 views

Ranking function approximation

I have a matrix function, which roughly looks like this: $$ Y_{i,j,k} = f(coef, A, B) = coef[i] * A_{i,j} * B_{i,k} $$ ...
1
vote
2answers
44 views

What algorithm to use for this problem?

I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it ...
0
votes
0answers
7 views

In multithreaded computations, how does parallelism, slackness and speedup affect the running time?

In the CLRS book it mentions that during some world-class multithreaded chess-playing program, developers had to prototype their program on a 32-processor computer then run it on a supercomputer with ...
0
votes
1answer
24 views

Mixed integer non convex optimization problem

If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. ...
0
votes
1answer
58 views

Pandemic board game - find all possible next 4 actions

I hope I am asking this on the right community. I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and ...
0
votes
0answers
32 views

Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
3
votes
0answers
23 views

Rearrange items in order reduce fragmentation and reduce wasted space

I have a segment with some offsets at irregular intervals There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset. Items are free ...
0
votes
1answer
26 views

Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions: There are "n" jobs which are distributed over the city. Company has "k" available workers. Each worker can do "x" jobs per day. "x" is dependent to the worker skills and the distance ...
2
votes
1answer
14 views

Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
1
vote
0answers
35 views

Weighted Activity Selection Problem with allowing shifting starting time

I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists. In my case, I am allowed to ...
3
votes
1answer
48 views

Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
0
votes
0answers
13 views

Can one pose an optimization problem as a problem in machine learning?

There seems to be an increasing trend towards posing problems in the realms of classical optimization theory as machine learning problems. Can you explain when one would resort to using machine ...
0
votes
0answers
19 views

Dynamic programming algorithm with an O(n) performance that will give the optimal solution

I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...
1
vote
0answers
20 views

Is there a way to *round* a nearby point into the feasible set?

Let $P \subset \mathbb R^d$ be a polytope with interior given by $F$-many linear inequalities. Suppose we have a convex problem with feasible set $P$. For example computing the Euclidean projection of ...
1
vote
0answers
33 views

How Expensive is Projecting onto a Polytope?

I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
0
votes
0answers
21 views

is the complexity of an algorithm connected to the “classification” of a optimization problem?

I wonder if the complexity is connected to an optimization problem. In general but also specifically e.g. when having a look at $ O(n^2) $. Does this just describe the complexity in general or does it ...
0
votes
0answers
27 views

Solving the 0-1 Multiple knapsack problem via Dynamic programming?

I want to code a variant of 0-1 Multiple knapsack problem via Dynamic programming. Problem: Given a set of n items and a set of m bags (m <= n), with ...
4
votes
0answers
40 views

Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
1
vote
1answer
63 views

How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?

Here is the problem: Input: A series of source/sink nodes at fixed positions with given outwards/inwards flow Edges are NOT specified. The edges can connect any nodes. The total source and sink ...
1
vote
0answers
91 views

Finding bounded lexicographically largest string of digits but not larger than other with counted substitutions

The problem comes from the book текстовые и жадные алгоритмы (String and greedy algorithms) by a fairly unknown Russian computer scientist Николай Сухоруков. We are given two numbers $A$ and $B$ of ...
1
vote
1answer
26 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
0
votes
0answers
23 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
1
vote
1answer
27 views

Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
3
votes
1answer
37 views

Is unconstrained quadratic programming NP-hard?

I could not find the answer on the Internet. The case of quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But ...
2
votes
1answer
67 views

Algorithm for dividing items into buckets while minimizing total weight

Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of ...
0
votes
1answer
95 views

How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an ...
0
votes
0answers
46 views

Making change optimally

Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j&...
1
vote
0answers
15 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
1
vote
1answer
23 views

Modifying the genetic algorithm

I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm. I have 3 "areas" of optimization, say parameters ...
1
vote
1answer
37 views

Is Newton's algorithm really this much better than conjugate gradient descent?

I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm. I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, ...
2
votes
1answer
27 views

Select certain number of column elements of a stochastic matrix, maximum one element per row

Consider a $m \times n$ Matrix. Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose ...
1
vote
1answer
32 views

Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
1
vote
0answers
36 views

About Steiner tree problem in graphs

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the ...
0
votes
2answers
48 views

How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
1
vote
2answers
27 views

How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
5
votes
2answers
194 views

If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
1
vote
2answers
38 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
1
vote
0answers
48 views

Max sum of k contiguous subarrays

The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...
1
vote
1answer
58 views

How can I calculate the maximum sum/product of sequence?

I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...