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
68 views

Debugging the issues on Megiddo's algorithm

I have done code for the algorithm to obtain the Optimal Basis but as I calculate the optimal solution $Xb=B^{-1}b$, I only get the correct value for some of the variables. For some variables, $Xb_i$ ...
0
votes
0answers
25 views

Arranging cubes in bins to minimize expected variation ratio

I am working on an optimization problem. Let's say we have a grid of bins where solid metal cubes could be placed. We have a number of colored metal cubes to be arranged in the bins. Each of these ...
0
votes
1answer
79 views

Find hamming codewords in r=2^k dimensions

There is the original problem, and an equivalent problem. The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, ...
0
votes
0answers
121 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 ...
0
votes
0answers
66 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 ...
0
votes
0answers
73 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 ...
0
votes
0answers
229 views

Seating-Chart Optimization

Does anyone have any ideas on a seating chart optimization formula for a call center environment? There are "docks" in which the workers sit. Each dock has approximately 15 seats, some more some less. ...
0
votes
0answers
47 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
0
votes
0answers
273 views

Eggs and Floors Puzzle - Alternate

Recently I've run across the "Two eggs, 100 floors" problem: You are given two eggs, and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which ...
0
votes
0answers
116 views

Algorithm: How many symbols of occurence k fit into b buckets under condition

I have the following problem to solve: Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size. Place a total ...
0
votes
0answers
96 views

Job Scheduling: Two Resources, Defined Job Length, Defined Earliest Start

Problem I stumbled over the following job scheduling problem. There are two resources, for simplicity I call them ... CPU_RAM (MAX_CPU_RAM specifies what is available in total) GPU_RAM (MAX_GPU_RAM ...
0
votes
0answers
11 views

Is maximising (or minimising) something enough to say that I am solving a decision problem? [duplicate]

We know that every optimisation problem has an equivalent decision problem. So say I keep going up a mountain (I.e. I am maximising my altitude) following a certain number of finite steps (similarly ...
0
votes
0answers
673 views

Traveling Salesman problem solution for small graph?

So let's say i have a graph like this and salesman starts his journey at "A" How do i solve the TSP problem for this graph with pen and paper on exam?
0
votes
0answers
161 views

Non-convex optimization problem over graphs

Given integers $m,n$, I want to compute the maximum possible value of $\Phi(G)$, over all simple, connected, undirected, unweighted graphs $G$ with $n$ vertices and $m$ edges. The objective function $...
0
votes
0answers
64 views

What's the complexity of the problem of optimally distribute n balls in m boxes?

Assuming that there is a function $f(x)$ (non linear, non convex) where $x$ is the vector $[n_1,n_2,\dots n_m]$ where $n_i$ is the number of balls in the box $i \in \{1,\dots m\}$, and $\sum \limits_i^...
0
votes
0answers
70 views

Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
0
votes
0answers
907 views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
0
votes
0answers
84 views

Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
0
votes
0answers
89 views

Parallel Machine Scheduling test data

I am writing optimization program for unrelated parallel machine scheduling problem on CUDA. Now, the only thing I am missing are some test cases. Does anyone know where I can find such data? I have ...
0
votes
0answers
84 views

Writing linear programming constraint in a canonical form

I have a particular research problem that I'm formulating as a linear program. It's more or less an instance of the transportation problem, except there is one additional constraint that is proving ...
0
votes
0answers
187 views

Complexity of active set method for Quadratic Programming

The Quadratic Programming problem is as follows: $$\min_x \{\frac12x^THx+x^Tg\}$$ $$Ax\le b$$ where $H$ is symmetric and positive semi-definite. What is the complexity of the active set method for ...
0
votes
0answers
35 views

Global minimum when noisy estimates of function available

I am interested in knowing about algorithms for finding global minimum when noisy estimates of the function are available.
0
votes
0answers
49 views

optimal path for traversing nodes

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
0
votes
0answers
71 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
144 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
44 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
236 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
45 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
31 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
39 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
317 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
140 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
194 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
3answers
1k views

Divide N sticks among M boys as homogeneously as possible (ignoring order)

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 ...
-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
83 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
229 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
72 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
264 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
118 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
346 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
38 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
684 views

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

The question is right there above.
-1
votes
1answer
71 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
478 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
383 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
0answers
22 views

mathematical formulation complexity

How to find the complexity of a mathematical formulation ( in terms of constraints and variables) (We refer generally to the notation (o(n^2) variables and o(n^3) constraints) ( I would be grateful if ...