Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
25 views

weighted graph separation algorithm proof

I have a graph G (G=(V,E)), where each edge has a non negative weight to it. My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
user avatar
2 votes
1 answer
66 views

Efficient algorithm to count number of intersections of n sets

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets. Example: Set a = [...
user avatar
  • 23
1 vote
1 answer
16 views

A lower bound for the makespan of heterogenous fog nodes

Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.
user avatar
  • 25
0 votes
0 answers
31 views

Find The Least Waste When Sawing Wood Planks In A Specific Order

Similar to one of the questions that was posted here roughly 4 years ago. Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 50cm 30cm and 20cm. What kind of bottom-up ...
user avatar
1 vote
0 answers
22 views

Minimize sum of products of partition [closed]

I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \...
user avatar
  • 11
1 vote
1 answer
41 views

Algorithm to compute cheapest path between two pixels in an image

I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is ...
user avatar
0 votes
0 answers
59 views

Solving Scheduling Problem With Gradient Descent?

I try to solve some kind of scheduling problem and wonder if there exists any theory or implementations already. Assume my shop receives a set of orders $o\in O$, each of which consisting of a ...
user avatar
  • 215
0 votes
0 answers
35 views

are computer errors inevitable?

this is my First post,I apologize for my ignorance. The question is: Could a programmer (human or Ai) with all the computing power and infinite time create a simulation of a world with our same laws ...
user avatar
0 votes
3 answers
68 views

Compute a commutative and associative operation on n-2 arguments efficiently

Considering a function $f$ such that: $$ f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3)) $$ and $$ f(x_1, x_2) = f(x_2, x_1) $$ and a set $X = \{ x_1, \dots, x_n \}$; how to compute $$f(...
user avatar
  • 103
1 vote
0 answers
61 views

Minimum swaps to rearrange array so that the same numbers are in consecutive positions

Problem: Given an array of $N$ integers in range $[1,M]$, count the minimum number of swaps to rearrange array such that the same values are in a row. For example, given an array $[1,2,1,1,2,1,2]$. ...
user avatar
  • 161
0 votes
0 answers
27 views

Identifying the parameters and finding an optimal solution to a problem

I work in the Computer Graphics field, and I have a problem where I need to find the optimal solution for, but I'm not sure how to best formulate the problem mathematically, how to define the ...
user avatar
0 votes
1 answer
30 views

Complexity of the partition problem with additional constraint

The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
user avatar
0 votes
1 answer
35 views

Printing an array using recursion

Printing an array using recursion is much slower as compared to printing an array using iteration. Why? Is iteration always faster than recursion?
user avatar
0 votes
0 answers
13 views

On the bounds of number of iterations of generative adversarial networks

I've been wondering whether there is any analysis on the bounds of number of iterations of generative adversarial networks (GAN), where here 1 iteration refers to 1 step of generator + discriminator. ...
user avatar
0 votes
0 answers
12 views

What is the difference between Optimal Control and Dynamic Programming?

I am reading Reinforcement Learning by Sutton and Barto, in which they mention dynamic programing and optimal control very often and as two different approaches. I wonder, what are the commonalities ...
user avatar
  • 13
0 votes
0 answers
10 views

Cutting stock problem upper bound with gilmore and gomory

I am trying to implement this article https://arxiv.org/pdf/1905.04897.pdf (the article is there only for information, no need to read it to answer my question) At some point they say when talking ...
user avatar
0 votes
0 answers
16 views

Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?

Disjoint Group Steiner Tree (DGST) is the following problem: Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
user avatar
0 votes
1 answer
20 views

Multi Objective Optimization Using Only Single Objective Optimization Algorithms

Let's say there is a single objective optimization problem SP (e.g. a linear program) and an optimization algorithm SA for it (e.g. simplex). Then applying SA to SP yields an optimal solution ...
user avatar
3 votes
1 answer
74 views

Allocating m rooms of varying capacity to n booking requests of varying sizes

I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize ...
user avatar
1 vote
1 answer
33 views

Find the largest subset of unpaired elements [duplicate]

I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired? Example ...
user avatar
  • 113
1 vote
1 answer
22 views

Pair points between to sets minimizing the global distance

I have two set of points in the plane or space, which could be for instance radar contacts over two successive scans. I'd like to pair them so that the sum of squared distances is minimal. One ...
user avatar
  • 111
1 vote
2 answers
51 views

Optimizing an arbitrary function of 10 variables

Let us be given a function $f(x_1,\dots,x_{10})$ of multiple variables $x_1,\dots,x_{10}$ given that $\sum_{i=1}^{10} x_i \leq 7$. How do we solve the following problem? $$ \begin{equation} \begin{...
user avatar
1 vote
1 answer
33 views

How to evaluate the tightness of a bound on a function?

I recently submitted a paper where in part of the paper I derived a bound on a function (note it is an upper bound). The benefit of the bound is that it is much less complex to compute in contrast to ...
user avatar
  • 153
0 votes
0 answers
21 views

Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
user avatar
0 votes
1 answer
36 views

What is this task type?

There are people and the food they prefer: John -20> Apple John -10> Pear Ethan -20> Apple Ethan -5> Orange Michael -10> Pear Michael -10> Limon The numbers indicate how strongly ...
user avatar
0 votes
0 answers
7 views

Stopping criteria for SMO when no solution exists for Hard Margin SVM

When we solve the dual problem using SMO, we pick two μi's at a time and optimize the dual wrt them while satisfying the required constraints. But in case we are using the no slack formulation of the ...
user avatar
1 vote
1 answer
37 views

Complexity of Nelder-Mead Algorithms

If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the ...
user avatar
0 votes
0 answers
68 views

What is the most computationally efficient Turing complete system?

I'm making a program that involves making models of and working with arbitrary systems (or programs). What is the most computationally efficient Turing complete system to model these in? By "...
user avatar
1 vote
1 answer
53 views

How to partition N numbers into K groups with constraints on the size and sum of each group?

Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n_k$ ...
user avatar
  • 13
0 votes
0 answers
20 views

In Viterbi's algorithm what is the difference between the observation space and the sequence of observations?

Wikipedia has an explanation for the viterbi algorithm, in particular it describes the following summary of the inputs: What is the difference between O and Y? Also I am trying to understand what the ...
user avatar
  • 133
1 vote
1 answer
106 views

Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
user avatar
0 votes
0 answers
7 views

Reporting mean instead of (highest) mode of solutions to a stochastic optimization problem

When running stochastic optimization search algorithms like genetic algorithms (GA), we often find several plausible local optima that satisfy our search problem of interest. In this case, we often ...
user avatar
2 votes
0 answers
50 views

Find minimum difference between pairs of numbers chosen from array of ranges

I recently thought of this problem, and I think it's very interesting. We are given an array of $N$ numbers, but we don't know the numbers themselves, only a possible integer range for each number. ...
user avatar
1 vote
1 answer
21 views

Lagrange Multipliers and Hard Margin SVMs

With hard margin support vector machines (SVMs), it suffices to find the critical points of the Lagrangian $L = \frac{1}{2}||\theta||^2 - \sum_{n=1}^{N} \alpha_n (y^{(n)} (\vec{\theta}^T\vec{x}^{(n)} +...
user avatar
0 votes
1 answer
39 views

Remove number after duplicated number

I created an algorithm which I cannot resolve. Imagine you have list of number like: val list = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9) And if some number is ...
user avatar
  • 101
0 votes
0 answers
11 views

How to evaulate the upper-bound for a multiobjective optimazation problem?

Given a product set $P$, where each product $p_i \in P$ has a cost $p_i.\!c$ and a value $p_i.\!v$. Therefore, $\forall p_i \in P$, $p_i.\!c > 0$ and $p_i.\!v > 0$. The cost-efficiency of a ...
user avatar
  • 1
3 votes
0 answers
58 views

Low-rank matrix completion is NP-hard

In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
user avatar
1 vote
1 answer
34 views

Binary matrix optimization problem with element co-dependence

Suppose we have an optimization problem where we want to find a binary matrix $A \in \{0, 1\}^{n \times m}$ that minimizes the score function defined as $$S(A) = \sum^n_i \sum^m_j f_{ij}(a_{i-1j}, a_{...
user avatar
  • 123
1 vote
2 answers
38 views

How to find the temperature scheduling for simulated annealing?

I have a combinatorial optimization problem that I try to solve using simulated annealing. It is about finding the optimal configuration of N points on a grid. I have the operation swap (swap one ...
user avatar
1 vote
2 answers
46 views

Space-efficient way to prove that a data has been processed before

Suppose that I have a stream of data packets in the form of unsigned 64 bit integers. And I want to make sure that I am not processing the same packet content more than once. A way of doing this would ...
user avatar
  • 11
2 votes
1 answer
36 views

Maximum Intersection of Convex Partitions

Given a bounded, convex polytope $C \subset R^d$, I have $n$ partitions of the polytope $C$ into at most $m$ smaller polytopes (disjoint on all but sets of measure zero). These smaller polytopes have ...
user avatar
2 votes
1 answer
34 views

From a directed graph (A), produce an undirected graph (B) with an edge for at least one outgoing edge for every vertex in A, minimizing edges

Problem: Given a directed graph $A$, produce an undirected graph $B$ with the same vertices and minimum number of edges satisfying the following constraint: For each vertex in $A$, at least one ...
user avatar
  • 31
1 vote
0 answers
46 views

Solution methods for this Weighted Partial Set Cover-ish problem

Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
user avatar
  • 183
0 votes
0 answers
16 views

How to "sort" stops when combining multiple bus routes (joint timetable)?

In a public transport system, it can happen that trips with partially different routes are written on one timetable. For example, if TRIP 1 has stops A-B-C-D and TRIP 3 has stops A-B-C-E, then the ...
user avatar
1 vote
1 answer
30 views

Optimal prune of a mutually-exclusive bipartite graph

I start with a complete edge-weighted unbalanced bipartite graph. For a known, fixed $n$ on the order of 1000: $$0 \lt n, n \in I$$ Left and right cardinalities might not be equal; for sides $U$ and $...
user avatar
0 votes
0 answers
26 views

Algorithm to find trinary code for given alphabet

A friend sent me this question and I've been stuck on it so if anyone could help I'll be thankful. Reminder: As we know Huffman coding is a lossless data compression algorithm. The most frequent ...
user avatar
4 votes
3 answers
528 views

Genetic algorithms applied to topological orderings of a DAG

I need to solve an optimization problem, whose search space is all possible topological orderings of a DAG. There is a cost function associated with each ordering, which has no simple mathematical ...
user avatar
  • 161
0 votes
0 answers
8 views

How to Find the Dominant Solution in Multi-Objective Optimizatiın Problems?

I am trying to run the simulated annealing algorithm for a multi-objective problem but I can not be sure how to check the domination between on two solutions. The objective funchtions are these: funch ...
user avatar
0 votes
1 answer
39 views

Using an optimal number of agents, maximise coverage of an area while minimising distance travelled

I'm a CS Year 2 student working on a team project which requires a solution to the following problem: Given a starting position on the edge of an irregular shape (example above) and a maximum number ...
user avatar
0 votes
0 answers
27 views

Optimal text/code formatting with alignment constraints

Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. ...
user avatar
  • 3,738

1
2 3 4 5
33