# Questions tagged [optimization]

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

1,392 questions
Filter by
Sorted by
Tagged with
2k views

### Can we create faster sort algorithm than O(N log N)

I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$ Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort ...
64 views

### Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope

I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve \...
46 views

### Can Homotopy Type Theory be used to derive more efficient algorithms on more efficient data representations from less efficient ones?

I've read here that in HoTT, compilers could swap out less efficient representations of data for more efficient ones and I'm wondering whether my interpretation of that statement is correct. Say we ...
17 views

### Best way to preserve SSD health when performing routine delete operations?

I'm coding an application with a mechanism that performs routine disk cleanup (on smartphone devices, which all use solid-state drives). I want to limit the disk usage to a certain threshold and see ...
34 views

### Constrain traveling salesman: visit a given city within a given distance from start

I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there ...
50 views

### 2D packing in fixed dimensions rectangle

Input: a enclosing rectangle of size $(W, H)$ a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$ Output: a scaling factor $s$ a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$ I ...
44 views

### Find the n best choices while maximizing value

Given: A list of slots (A, B, C, ...) Every slots supports a list of choices (C0, C1, C2, C3...) Every choice has a value All slots must be filled with at most n different choices. The sum of the ...
27 views

### Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming

I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems. I have gone through the standard questions such as 0-1 Knapsack and Coin Change ...
49 views

### How to solve the bin packing problem with conflicts?

I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC). The problem is defined as follows: consider a set $V$ of $n$ items, where ...
35 views

### Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?

So let's say I'm baking a cake and it has a few ingredients (including multiples): ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg} I can ...
49 views

### Is there a dynamic programming solution to the student allocation problem?

The student project allocation problem I am trying to solve goes as follows. There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$. Each student makes a top $3$ of their ...
721 views

### Fast algorithm for clustering groups of elements given their size/time

I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can. I would like to cluster files into the specified number of groups, ...
63 views

### Trees with duplicate nodes and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
29 views

### Responsive input sliders - is there a better way?

I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output ...
24 views

### A version of TSP where there is a probability each node is visited?

A friend in industry proposed a problem to me. If you have a supply warehouse, you can treat each station with products as a node. Each node has a probability it will be visited by an employee working ...
55 views

### How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
35 views

1k 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 (...
1k views

### Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
383 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). ...
25 views

### Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
33 views

### How do I optimize a set of sub-lists which can combine to recreate higher level lists?

I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list ...
431 views

### Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
53 views

### Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
26 views

### Weighted interval set scheduling problem

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is ...
31 views

### Partially defined boolean function

Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
25 views

### “Low-High” sort divide and conquer with merge… how small to make the subproblems for good efficiency?

For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So ...
369 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"...