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
0
votes
1answer
334 views

Are most metaheuristic algorithms different metaphors for the same method?

Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to ...
1
vote
0answers
127 views

Bidirectional Search on possible negative weight edges digraphs

There are plenty material about bidirectional search with non-negative edge weights. One example is this paper. I am looking for any improvements using a bidirectional approach for acyclic digraphs ...
12
votes
3answers
2k views

Optimal strategy for an abstract game

I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A_0$. (E.g. $A_0 = 1234$.) ...
1
vote
1answer
69 views

Select largest subset, subject to a separate weighting constraint

Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that: $$ maximize\sum_{i=1}^k c_i \\ \sum_{i=1}^k w_i \ge W $$ It seems pretty simple at first. ...
1
vote
1answer
24 views

Optimizing for maximum intervals given a distance bound

Given an interval set $X = \{(s_1, e_1), \dotsc, (s_N, e_N)\}$ ordered such that $s_i \leq s_j$ and $e_i \leq e_j$ for all $i < j$ and an integer $b$, I would like to find a maximum sized subset $X'...
2
votes
1answer
100 views

Finding maximal independent sets in an independence system

An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent. Suppose I have an oracle for testing ...
0
votes
0answers
74 views

Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
-1
votes
3answers
254 views

Finding best three numbers of an array

Given a sorted array of $n$ integers ,and some other integer $m$, find the $3$ numbers in the array $x,y,z$ such that $x+y+z\ge m$,and their sum is minimal. If there are no such,return null. Any ...
2
votes
1answer
87 views

Optimal insertion of edges for a graph [closed]

I am working on a problem which could be reduced to a graph optimization problem as below. A set of colored nodes is given. The edges are to be inserted between the nodes. A node can have only 4 ...
1
vote
2answers
70 views

Real-valued genetic algorithm offspring out-of-bounds

I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, ...
2
votes
1answer
1k views

Efficient Algorithm to compute radius of tree

Given an acyclic undirected graph alike to this one : (Here the center is the node '2', and the radius is 5) What is the most efficient (ideally in O(n)) way to ...
1
vote
1answer
51 views

Maximizing the boolean combination of given real numbers with dependencies

Let $x_i,x_{ij}\in\mathbb{R}$ and $b_i\in\{0,1\}$ for all $i,j\in\{1,2,\ldots,n\}$ and $j>i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: ...
0
votes
0answers
58 views

1 + ε approximation for non linear program

Let us assume that we have the following (non linear) program : R = min { ( (c1^T)*x + d1 ) / ( (c2^T)x + d2 ) : Ax<=b , (c2^T)*x+d2>0} We also assume that the feasible solution area is bounded ...
1
vote
1answer
103 views

Which algorithm suits this problem best?

I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following: There are several points of interest (POI), each has a value (for the user), ...
2
votes
1answer
26 views

How to show that there are $\binom{M+K}{M}$ different number of type bins?

In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma. Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the ...
0
votes
0answers
72 views

Applying Ford-Fulkerson to settle a business lunch

I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize ...
1
vote
0answers
141 views

Edge coloring optimization using dynamic programming

The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than ...
2
votes
1answer
97 views

route and/or packing optimization algorithm

What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it? Given: a list of items each with a ...
5
votes
2answers
92 views

Algorithm for choosing unique options with least overall cost

Problem And Question I am looking for pointers for an efficient algorithm for the following problem. It is hard to explain without some data so first I will provide some example data: Destination 1:...
3
votes
1answer
101 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
3
votes
1answer
198 views

Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $...
1
vote
1answer
82 views

Maximizing the boolean combination of given real numbers

Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$, $$...
4
votes
1answer
178 views

Distributing resources for maximum gain

This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it. Suppose there is a collection of shared resources, and a collection of possible ...
0
votes
1answer
64 views

Which class of neural network problem is this?

I have managed to describe a problem in quantum computing as the optimization of a function f(graph,vector), over graphs and real vectors. For a given graph, I can ...
4
votes
0answers
464 views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
0
votes
1answer
4k views

Difference between fractional knapsack & greedy solution

I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem ...
1
vote
1answer
70 views

Why is this greedy algorithm claim true?

I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize ...
1
vote
0answers
431 views

Step size choice with l-bfgs

I'm trying to implement L-BFGS but I can't quite figure out how to do step sizes. I tried small fixed step sizes, but for some reason the iterates always explode whenever memory < variable size (...
1
vote
0answers
79 views

Bin Packing across multiple iterations

I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given ...
11
votes
5answers
8k views

Data Science vs Operations Research

The general question, as the title suggests, is: What is the difference between DS and OR/optimization. On a conceptual level I understand that DS tries to extract knowledge from the available data ...
1
vote
0answers
117 views

Genetic Algorithm for maximization

this may be a shot in the dark, but I am trying to teach myself more machine learning concepts. I have found a textbook and am trying to work through the exercises in it. Could anyone help me with ...
1
vote
0answers
63 views

Difference between Memetic and Cultural algorithms

What is the difference between a memetic algorithm and a cultural algorithm? I mean they're both evolutionary algorithms where they select a subset of the population to apply some local search logic. ...
2
votes
0answers
219 views

Geometric interpretations of midpoint algorithm, homogeneous linear least squares and nonlinear least squares method in 3D reconstruction?

In "Multiple View Geometry in Computer Vision" Chapter 12. Structure Computation, page 310-313, triangulation is used for point 3D reconstruction. There are three methods mentioned: Midpoint method ...
1
vote
2answers
180 views

What is the name for polynomially solvable optimisation problems?

An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known. Symmetrically, ...
5
votes
1answer
247 views

Maximize product of sum of two subset

Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize $$ \left(\...
3
votes
4answers
175 views

Optimization problem where penalty is sensitive to permutation

Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I ...
1
vote
0answers
22 views

optimization problem: Find Phase of input for minimized max output [closed]

Let the $\textbf{bold characters}$ represent the vectors/matrices.All the vectors/matrices/scalars only refer to real numbers. In a continuous LTI system. $\frac{d\mathbf{T}(t)}{dt}=\mathbf{A}\...
4
votes
0answers
124 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 ...
7
votes
1answer
3k views

BFGS vs L-BFGS — how different are they really?

I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum ...
0
votes
1answer
124 views

How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started ...
0
votes
2answers
169 views

Design Hashing function from known distribution of bits to be set

How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash ...
2
votes
2answers
602 views

Worst case using the first fit $2$-approximation for the bin packing problem

I am with the phone so I would be more verbose when I will have a pc on hand, if you desire. The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the ...
5
votes
1answer
1k views

How can I restructure matrices to have non-zero elements close to the diagonal?

I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members ...
-1
votes
2answers
147 views

Algorithm to allocate resources to minimize the maximum of any party

I was given the following algorithms problem: Suppose you have $n$ cities. Each city $c_i$ has population $p_i$. You want to construct $m \geq n$ schools, where each school can only serve ...
0
votes
1answer
54 views

Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do ...
2
votes
0answers
64 views

Finding the smallest tree of given weight

Take a node-weighted, undirected graph $G$, and a node $r$ in $G$. Is there an efficient algorithm to find a tree in $G$ rooted at $r$ which has total weight at least $w$ and contains a minimal number ...
2
votes
1answer
213 views

Minimizing transportation cost through a network, multiple source/sinks

I have the following problem: Inputs: A finite collection $V$ of vertices A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$) An amount of ...
0
votes
1answer
38 views

Optimizing estimator of composed functions when function is known

I have a problem which I'm looking to see if there is literature on: Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator ...
4
votes
0answers
206 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 ...