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
41 views

interval scheduling variant: 1 machine with 2 tasks need to complete only

I am looking for an optimal solution of an interval scheduling variant. Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum ...
1
vote
1answer
39 views

Are there search algorithms that perform better on a Rope than a String?

I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not ...
2
votes
2answers
801 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 : ...
1
vote
0answers
45 views

Looking for an algorithm or similar mathematical problem for trading ownerships in shared property

Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $...
1
vote
0answers
35 views

Minimun k-union from a different angle

I'm looking for work done on solving some problem which is very similar to the minimum k-union. The problem: There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,...
4
votes
1answer
259 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
0answers
36 views

Graph problem / Dynamic graph

I have been trying to come up with an efficient algorithm for the following problem. Let $G = (V,E)$ be an undirected acyclic weighted graph, where there is exactly one path from a vertex $u$ to any ...
1
vote
0answers
20 views

Complexity of maximization of entropy of Hamming distance of bitstrings

We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \...
0
votes
0answers
36 views

Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-...
2
votes
1answer
120 views

Image registration using gradient descent

I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$ I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{...
1
vote
1answer
51 views

Feeling guilt tripped in linked list

Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list. Now, what I do while implementing most ...
1
vote
2answers
60 views

Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

I'm trying to prove a greedy algorithm works for a specific problem: You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run ...
3
votes
1answer
54 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: ...
9
votes
1answer
200 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
0
votes
1answer
200 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:/...
3
votes
2answers
656 views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
1
vote
1answer
148 views

Knapsack Problem with exact required item number constraint

How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight ...
0
votes
0answers
30 views

Solving NP problems : analogy between the SAT problem and the shortest path problem

in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences), whose purpose is to show how a SAT problem can ...
1
vote
1answer
2k 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
19 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 ...
1
vote
1answer
25 views

How can I optimise this bitmask generation algorithm?

I am emulating the left shifting of a 128-bit integer using two 64-bit integers. For this I must calculate the bits that need to be moved into the higher portion. I have the following algorithm for ...
2
votes
1answer
108 views

Knapsack-like problem with profit formula

Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...
2
votes
1answer
18 views

How to be sure of a good solution in hyperparameter optimization

I have a very expensive black-box function and at least 15 parameters that I want to explore (usually 5-6 at a time). So far I have tried Genetic Algorithms and Gaussian Process Surrogate Optimization ...
7
votes
1answer
338 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
19 views

Matching vertex values with sum of edge weights on bipartite graph

Earlier this week I asked this question (please review): Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags. ...
0
votes
1answer
80 views

taking school courses efficiently

I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number, professors needed here. just my selected courses I know will allow me to ...
1
vote
0answers
15 views

Queries on unbounded knapsack

Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
1
vote
1answer
104 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
107 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 ...
2
votes
1answer
33 views

Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm

I have a collection of $n$ vectors $x_1, ..., x_n \in \mathbb{R}_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to ...
2
votes
2answers
136 views

Distribution Optimization Algorithm

I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem). Problem Imagine StackOverflow started offering a subscription where ...
3
votes
1answer
2k views

Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the ...
1
vote
0answers
29 views

What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?

Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem). A trivial ...
0
votes
1answer
69 views

What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
2
votes
1answer
4k views

Single Source Shortest Paths using Product Construction

I am trying to solve a bounded SSSP problem as follows: Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with ...
3
votes
2answers
434 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
1answer
201 views

Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm

I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to ...
0
votes
0answers
19 views

ILP formulation question

How to formulate the following constraint in ILP? if i-1 <= x <= i+1 then y < 5 end if So basically if the x is ...
1
vote
0answers
23 views

Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
0
votes
1answer
29 views

simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
2
votes
0answers
58 views

Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $...
1
vote
1answer
98 views

Array segmenting algorithm

I have a sorted array of integers [x, ..., n, ..., y] so that x > 0 n - x = random positive integer The array might look something like this: [1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126,...
2
votes
1answer
38 views

Finding largest sum of $k$ elements below threshold

I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of ...
3
votes
1answer
53 views

Minimize function on permutations

Problem: Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$...
0
votes
0answers
17 views

algorithm for scheduling tasks based on constraints and feedback loop if possible

I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource. In other respects the tasks are independent of each other Each task is ...
11
votes
3answers
152 views

Minimum circles to cover a set of points and avoid another set of points

Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in ...
0
votes
0answers
19 views

Optimization Problem to Maximize Points Given Cost Constraints

I have 2 groups of items: A and B. Each item has an associated cost c i and points p i. I need to choose 3 items from group A, and 2 items from group B such that the sum of points of those 5 items is ...
1
vote
1answer
32 views

Multi-Path Length Minimization

I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents. Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
0
votes
2answers
2k views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
6
votes
1answer
80 views

Selecting vertices in a graph in an order to keep border vertices as few as possible

I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white ...

1 2
3
4 5
28