Questions tagged [optimization]

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

349 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
503 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
921 views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
697 views

3k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
805 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
608 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
179 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
261 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')$ ...
178 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
153 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
344 views

Trying to find a human-usable method to figure out optimal round 1 openings for this game

I'm trying to figure out optimal round 1 openings for this game: http://generals.io/. For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that ...
142 views

When does greediness guarantee optimality?

I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ...
224 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how many permutations would get rejected ...
119 views

39 views

Does it make sense to examine the dual of a feasbility problem?

Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
490 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
112 views

One-sided, distance-optimal polyline reduction to a given number of vertices

So I have been battling this rather peculiar problem: given the following input (on an euclidean plane): point p polyline l integer n p is not inside of the convex hull of l find a new polyline l', ...
65 views

Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
122 views

Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
200 views

Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
330 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"...
103 views

Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
214 views

Subset sum with wider constraint

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}$ subject to $\displaystyle\sum_{i} w_ix_i \leq W$ for a ...
2k views

Maximizing pruned branches in an alpha-beta tree

Preliminary After doing some searches of similar questions posted here and elsewhere, i feel like this is the right place to inquire about, now let's get through some boring main notations... A ...
228 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 ...
219 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
99 views

Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing ...
103 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
122 views

What is this prize-collecting optimization problem with travel times?

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. Recently,...
437 views

Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
23 views

Non-linear optimization of a family of functions

I'd like some advice about the following problem (resolution methods, problem category, etc.). The context is about the coregistration of several images all-in-once ($n$ images, $f_{i,j}$ the ...
38 views

Optimal flow in a network with non-constant edges' weights

I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
64 views

Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image ...
380 views

Optimal pairing of points in a set

I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the ...
382 views

Learning automata for degree constrained minimum spanning tree problem

I'm trying to understand the algorithm described in "Degree constrained minimum spanning tree problem: a learning automata approach" (Javad Akbari Torkestani, The Journal of Supercomputing; April 2013,...
40 views

Knowing if I have an optimal ordering for a OBDD

I'm learning about OBDD and I have learned that the size of a reduced OBDD (ROBDD) is dependent on the ordering of the variables, and that finding an optimal ordering is an NP hard problem. Say I ...
60 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
I'm trying to understand the following excerpt from a paper: Subproblem 1: computing $S$. The $S$ estimation subproblem corresponds to minimizing  \sum_{p}(S_p - I_p)^2 + \beta((\partial_xS_p -...