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
3
votes
1answer
49 views

Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some ...
0
votes
0answers
18 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
17
votes
13answers
10k views

Why do we need full-fledged workstations running massive OSes with massive software?

I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of ...
3
votes
2answers
924 views

Optimal meeting point

I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point ...
5
votes
4answers
1k views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
0
votes
1answer
28 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 ...
1
vote
0answers
37 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 ...
13
votes
2answers
1k views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{...
0
votes
1answer
157 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
49 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
41 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 ...
0
votes
1answer
31 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
7 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
26 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, ...
4
votes
2answers
262 views

search problem vs optimization problem

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question As I understand it, we can ...
0
votes
0answers
17 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} $$ ...
0
votes
1answer
27 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)$. ...
1
vote
2answers
57 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
1answer
223 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
17 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
0answers
33 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 ...
4
votes
1answer
50 views

Optimal flow in a network with non-constant edges' weights

I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
6
votes
0answers
595 views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
3
votes
0answers
26 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 ...
2
votes
1answer
16 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
39 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 ...
0
votes
0answers
17 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
25 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
39 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
76 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
47 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
79 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
96 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 ...
2
votes
1answer
75 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
27 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
42 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
104 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 ...
0
votes
0answers
56 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&...
2
votes
1answer
236 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
101 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 ...
6
votes
2answers
416 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
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
28 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
44 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
32 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
34 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)...
2
votes
1answer
274 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 2 3
4
5
28