# 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
204 views

### Optimal way for grouping events

I am creating an event notification system. Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped. All the events ...
146 views

### Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
352 views

### Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably close,...
109 views

870 views

### Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements: S = s1 ... sm T = t1 ... tm Semantically both sets are equal, but due to noise (...
139 views

### Shortest-depth routing algorithm

This problem came up in a graph network routing context, it can be expressed as follows: Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k \rangle$...
230 views

### Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
93 views

### Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be ...
33 views

### Choose m points out of n that form the polytope with the maximum volume in hyperspace

Let's say I have a set $A$ of $n$ points represented by real vectors of length $l$. What type of algorithm would I use to find the subset $B$ of $m$ ($m$ is arbitrary, to be chosen) points that ...
134 views

### What is the significance of the vector dimension in semidefinite programming relaxations?

Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you. So, we first write down an integer quadratic ...
552 views

### Distance k-Dominating Set on a Tree

I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an ...
144 views

649 views

### Finding a set of maximally different solutions using linear programming or other optimization technique

Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is ...
2k views

### How to pack polygons inside another polygon?

I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls. I can scan the leather sheets ...
270 views

### Algorithm for cost function maximization

I have a system that takes in 'm' inputs and provides a cost value as an output. The system is a "black box" to me. The inputs can be varied and the corresponding output can be observed, however, I ...
167 views

### What's the meaning of “Front” in “Pareto-Optimal Front”?

I'm reading a paper about Multi-Objective Optimization Problem. I understand Optimal in Pareto sense, and I even know what is Pareto-Optimal Front somehow. But I can't find a relationship between the ...
987 views

### Traveling Salesman: how to use a lower bound?

Let me preface this question by giving some helpful background material. I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
330 views

### Minimizing Cost by minimizing delay

There is a complete binary tree with its leaves as components of some system The values from one node to another gives propagation time for a signal to propagate from one junction to another For the ...
2k views

### Algorithm to match numbers with minimum number of moves

This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far. Given a series of numbers, e.g. ...
145 views

### Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization ...
25 views

### Is it possible to do reductions with non-decision problems? [duplicate]

I've recently begun studying reductions in my algorithms class. All the reductions I've seen have been from decision problem $\to$ decision problem. Is it possible to do reductions with non-decision ...
113 views

### What does “finding an optimal action” for a bandit mean?

In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an ...
84 views

### Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
182 views

### Gradient descent vs. Newton's method: which is more efficient?

Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
107 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality [closed]

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
14k views

### How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. ...
77 views

### How to optimally seperate a student body?

Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with ...
132 views

### Unknown notation “$e^T$” in a machine learning paper

I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained ...
2k views

### Automatic seat assignment algorithm [closed]

I am looking for articles relating to algorithms that deal with automatic selection of seating assignment. I need an algorithm (preferably more than one) that can automatically select a seating place ...
390 views

### Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
766 views

### Practical Application of Kadane algorithm

Kadane Algorithm is used to solve the maximum subarray problem which in simpler terms is to find the highest possible value of a continuous sub array in an array. One often cited application of ...
50 views

### Assigning packages to different points by minimizing distance: is this a known problem?

Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of ...
174 views

### Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
4k views

### What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer). What is the best way to ...
2k views

### Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ... ...