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
1
vote
1answer
14 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
19 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 ...
0
votes
0answers
14 views

Fuse 3D-Points in Bundel Adjustment? [closed]

(Crossposting from here: https://softwareengineering.stackexchange.com/questions/399331/fuse-3d-points-in-bundel-adjustment) I'm actually implementing my own Pose-Estimation/- and -Refinement ...
1
vote
1answer
23 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
25 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
39 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
46 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
92 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 ...
5
votes
2answers
117 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
14 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, ...
0
votes
1answer
27 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
2
votes
1answer
25 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
29 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
259 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. ...
11
votes
1answer
315 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
1
vote
0answers
32 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 ...
1
vote
1answer
39 views

Intuition behind this specific algorithm for time series

Going through the EPI book and I need some help understanding this part. There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The ...
0
votes
2answers
42 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
22 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 ...
1
vote
2answers
35 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
40 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
54 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 ...
11
votes
5answers
8k views

Data Science vs Operations Research

The general question, as the title suggests, is: What is the difference between DS and OR/optimization. On a conceptual level I understand that DS tries to extract knowledge from the available data ...
1
vote
1answer
17 views

Maximum-cardinality matching in unbalanced bipartite graphs

Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
0
votes
0answers
44 views

Verifying the minimum cost from each node to a sink node in linear time

Problem Statement: Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
6
votes
1answer
50 views

Perpendicular vectors out of a set

I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. ...
3
votes
1answer
19 views

Choosing which workers (limited number) to use in a binary assignment problem?

First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case. The problem: We are given a set of $m$ workers $A = ...
0
votes
0answers
25 views

Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
0
votes
1answer
135 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
0
votes
0answers
10 views

Given we restrict the time and memory allowed what bounds can we place on a halting decider?

If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ...
0
votes
1answer
25 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
1answer
725 views

Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
2
votes
2answers
296 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). ...
2
votes
1answer
48 views

Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
1
vote
1answer
47 views

Can an optimization algorithm be “universal”?

I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX. In trying to answer this question, I realized that I don'...
2
votes
0answers
33 views

Dynamic Program for this Weighted Possion-Binomial Problem?

Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
4
votes
1answer
330 views

Vehicle Routing Problem with multiple deliveries?

I have a problem that can be reduced to the following: There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points"...
2
votes
1answer
2k views

A variant of coin change problem

Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in ...
0
votes
1answer
165 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 ...
1
vote
1answer
189 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
1
vote
1answer
131 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
-2
votes
1answer
25 views

Question about complexity of TSP Optimization problem

Is this statement true? Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
1
vote
1answer
1k views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
2
votes
2answers
581 views

Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
4
votes
1answer
228 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given. For example ...
2
votes
2answers
82 views

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
2
votes
3answers
285 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 \...