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
0answers
69 views

Aliens to the Moon

$N$ Aliens want to reach their Moon ($D$ meters away), but they can only put on each other, making a vertical chain. Every $Alien(i)$ has an height $X(i)$ and a lenght of their arms $Y(i)$. ...
0
votes
0answers
143 views

Find all sets of n unique rows in matrix

I am looking for an efficient method to find all unique combinations of $n$ rows in a matrix. For example, if $n=6$, then I want to find all sets of 6 rows from the input set C in which the columns ...
0
votes
0answers
38 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
0
votes
0answers
41 views

Algorithms for keeping number of backups constant

The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
0
votes
0answers
215 views

Weighted Interval Scheduling with constraint

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do ...
0
votes
0answers
43 views

Complex 0/1 Backback Problem

Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total ...
0
votes
0answers
30 views

Finding the N'th viable combination between arrays A and B [duplicate]

To dumb it down to basics, lets say I have a struct called item that looks like this: struct item { int power, cost; }; then I have 2 arrays of these items, ...
0
votes
0answers
33 views

Prove a characterisation of the minimum directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
0
votes
1answer
37 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 ...
0
votes
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 ...
0
votes
1answer
315 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 ...
-1
votes
2answers
138 views

Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

One of my friends works for a big oil rafinery. He's in charge of optimising the inputs (volumes, maximum price to pay for crude oil etc.) given a profit. He's telling me there are heuristic ways to ...
-1
votes
2answers
167 views

Is there only one optimal BST?

as i read some material about Optimal BST, i ran into a trouble. for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand ! ...
-1
votes
1answer
42 views

Is a non-perfect improvement and optimisation?

In real word problems, the influence of multiple not perfectly known factors results in using heuristics instead of mathemacial solutions that calculates a perfect value from only precisly defined ...
-1
votes
2answers
80 views

Find the optimal way [closed]

We consider the TSP in Grid-City. The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system. The distance of $2$ points $C=(x,...
-1
votes
1answer
210 views

Where to learn about Short-circuit evaluation? [closed]

I would like to implement short circuit evaluation logic in my code. And I want to know about the full details how it works? Ex: function a() {return true;} function b() {return false;} function c(...
-1
votes
1answer
60 views

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

Recall the notion of NPO problem. An NPO problem is simple if the following is true: $\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$ In words, given any positive integer $k$, the ...
-1
votes
3answers
253 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 ...
-1
votes
1answer
86 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 ...
-1
votes
1answer
326 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 ...
-1
votes
1answer
37 views

Optimization problems and quantifiers

A simple optimization problem is of form $\max_{x\in\mathcal R}f(x)$. We can quantify as $\exists x\in\mathcal R\forall y\in\mathcal R f(y)\leq f(x)$. The quantification here is $\exists\forall$. ...
-1
votes
1answer
499 views

Best way to schedule jobs so as to get minimum average turnaround time [closed]

The question is right there above.
-1
votes
1answer
63 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
-1
votes
1answer
467 views

Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently? ...
-1
votes
1answer
352 views

Balanced partition problem for N =< 60 and very large sums

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under ...
-1
votes
1answer
42 views

Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...
-1
votes
2answers
144 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 ...
-1
votes
1answer
74 views

Algorithm : Select maximum number of Boxes to lift from N boxes

There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to ...
-1
votes
1answer
128 views

Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
-1
votes
1answer
111 views

ordered uniform distribution

We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ ...
-1
votes
1answer
169 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 ...
-2
votes
2answers
913 views

Divide N sticks among M boys as evenly as possible

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is ...
-2
votes
1answer
25 views

Question about complexity of TSP Optimization problem

Is this statement true? Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
-2
votes
1answer
129 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 ...
-2
votes
1answer
99 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
-3
votes
3answers
163 views

Building a Hyper Computer

I had an idea for a theoretical super computer. Supposing, one was able to optimise(or significantly increase efficiency) all algorithms used in most computing tasks(An open source project on ...