# Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

1,389 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 : ...
45 views

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 ...
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 ...
20 views

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:/...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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')$ ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
434 views

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,...
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 ...
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]$...
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 ...
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 ...
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 ...
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 ...