# Questions tagged [optimization]

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

1,410 questions
Filter by
Sorted by
Tagged with
1answer
156 views

### Fast solution for a combinatorial maximizaton problem

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (...
1answer
118 views

### Scalar by N component vector multiplication faster than O(N)?

Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar? It feels to me that there should be some exploit to do that. After all we will ...
1answer
108 views

### Integer Programming - packing wolves and sheep

I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and ...
1answer
1k views

### What is the advantage of Day-Stout-Warren algorithm for balancing BST?

While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time. In my opinion I can ...
0answers
271 views

### C++: Minimization Using Levenberg Marquardt to Solve for Two Variables [closed]

I am trying to solve this equation using C++: X and Y are both given sets of data. X = [x1, x2, ... , xn], Y = [y1, y2, ... , yn] a is a given integer. The goal is to find a pair z and k that ...
1answer
3k views

### How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves (...
2answers
230 views

### Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
1answer
732 views

### Find a quarrel-free seating order with a greedy algorithm [duplicate]

I'm revising for an Algorithms exam and looking at a sample question it says : A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy ...
1answer
13k views

2answers
1k views

0answers
302 views

### Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
1answer
598 views

### Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0answers
42 views

### Separate points inside set

I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ...
1answer
393 views

### Why would this Semidefinite Program be Dual Infeasible?

My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is ...
2answers
1k views

### Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
1answer
226 views

### How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
1answer
420 views

### What is the formal name for this algorithmic problem?

I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction. The problem is ...
1answer
290 views

### What is the Certificate for Set Cover?

Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, m\}$...
2answers
466 views

### Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
1answer
289 views

### Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
1answer
91 views

### Is ecological bin packing NP-hard?

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as: Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, ...
1answer
89 views

### What algorithm is suitable for very small scale, time dependent optimization?

I have a time-dependent (dynamic) optimization problem: $$f_t : [0;1]^2 \mapsto \mathbb{R}^+; t \in [1, \dots, n]$$ $f_t$ is to be maximized. That is for each $t$ I would like to find a relatively ...
0answers
25 views

### State of art quadratic knacksack algorithms

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
1answer
2k views

### Algorithm for finding best combination of elements

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C. The types come with expenses: Type A's are the least expensive, and C's are the most ...
1answer
346 views

### how to improve solution generated by greedy method for 0-1 knapsack? [closed]

I am working on 0-1 knapsack using greedy method, I have some problem in it. It's already proved that solution generated by greedy method for 0-1 knapsack is may or may not be optimal. If solution ...
1answer
132 views

### Dynamic Programming Approach

when we are trying to solve a problem with dynamic programming. we have to follow some general steps characterize the solution structure Recursively define optimal solution compute the value from ...
1answer
89 views

### How to order objects to minimize non-adjacency cost

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent ...
1answer
189 views

### What algorithms solve the minimun multidimensional multidemand 0-1 knapsack problem?

I've found an heuristic algorithm[scatter search] that solves the common version of MDMKP(MultiDemand Multidimensional Knapsack Problem)[the one that maximizes] but what about the minimize version? is ...
0answers
25 views

### Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each day,...
0answers
603 views

### Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
0answers
128 views

### In multi criteria decision making, what notions are there to get a subset of the Pareto set?

In the multi criteria decision making context, let $\mathcal{A}$ be a set of alternatives or choices. Each alternative $\alpha\in \mathcal{A}$ is a vector of $k$ criteria $\alpha=(v_1,v_2,\dots,v_k)$. ...
1answer
317 views

### Looking for an algorithm to solve a specific Vehicle Routing Problem

I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled. There is only ever 1 company warehouse in the area. The ...
1answer
156 views

### NP-hardness proof, what is wrong with it?

My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is NP-...
0answers
470 views

### Optimal vehicle routing on map

Currently I am developing a piece of software that solves the vehicle routing problem. The task is the following: I have several vehicles along the town I have lots of destination points along the ...
0answers
203 views

### Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
0answers
145 views

### What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
0answers
154 views

### Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ...
3answers
958 views

### Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...