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
12
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}^{...
1
vote
0answers
14 views

Proof of Fundamental Lower Bound on Regret

Specifically in the setting of Online Convex Optimization, Regret bounds are generally used to evaluate an algorithms performance. $\mathcal{R}_T := \sum_{t=1}^Tf_t(x_t) - \min_x \sum_{t=1}^Tf_t(x)$ ...
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
1answer
26 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;
0
votes
1answer
151 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
4
votes
0answers
25 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 ...
1
vote
1answer
1k views

Gradient descent overshoot - why does it diverge?

I'm thinking about gradient descent, but I don't get it. I understand that it can overshoot the minimum when the learning rate is too large. But I can't understand why it would diverge. Let's say we ...
0
votes
1answer
16 views

Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values ...
3
votes
1answer
55 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 \...
0
votes
0answers
16 views

How do i code Steepest Descent in python? [closed]

I am very confused and really need help to code with Steepest Descent method. I have a pseudo code for it( see picture).
7
votes
1answer
287 views

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
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
15 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
153 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
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
1answer
87 views

Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
0
votes
1answer
72 views

How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or ...
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)$. ...
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
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
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
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 ...
4
votes
1answer
45 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 ...
5
votes
0answers
469 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
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
22 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 ...
0
votes
1answer
44 views

Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
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 ...
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
25 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
90 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
22 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 ...
2
votes
3answers
2k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
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 ...
0
votes
0answers
45 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
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 ...