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

learn more… | top users | synonyms

1
vote
0answers
15 views

What algorithm is suitable for very small scale, time dependent optimization?

I have a time-dependent (dynamic) optimization problem: $$ f_t : [0;1]^2 \mapsto \mathbb{R}^+; t \in [1, \dots, n] $$ $f_t$ is to be maximized. Mostly $f_t$ is a relatively simple, continuous, ...
1
vote
0answers
9 views

State of art quadratic knacksack algorithms

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
-1
votes
1answer
46 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 ...
4
votes
1answer
16 views

How to order objects to minimize non-adjacency cost

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent ...
-2
votes
1answer
39 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 ...
3
votes
2answers
45 views

Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
-1
votes
1answer
9 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 ...
1
vote
0answers
20 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each ...
3
votes
1answer
48 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq ...
2
votes
0answers
55 views

Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
0
votes
1answer
34 views

Assuming finite optimal cost of a specific LP, find an optimal solution directly

Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$. Derive a simple test for feasibility of this problem Assuming the optimal cost is ...
4
votes
3answers
139 views

Cutting equal sticks from different sticks

You have $n$ sticks of arbitrary lengths, not necessarily integral. By cutting some sticks, you want to get $k<n$ sticks such that: All $k$ sticks have the same length; All $k$ sticks are at ...
0
votes
1answer
95 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 ...
3
votes
0answers
56 views

What is this discrete/combinatorial optimization problem?

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. ...
2
votes
0answers
57 views

Optimal vehicle routing on map

Currently I am developing a piece of software that solves the vehicle routing problem. The task is the following: I have several vehicles along the town I have lots of destination points along the ...
4
votes
1answer
107 views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
0
votes
0answers
49 views

A Fast Algorithm to Approximately Solve a Modified Version of The Thomson Problem

The problem I'm trying to solve is the same as the Thomson Problem except that the objective isn't to minimize $$ U(N) = \sum_{i < j} \frac{1}{r_{ij}}, $$ given $r_{ij} = |\mathbf{r_i} - ...
3
votes
0answers
45 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
11
votes
2answers
242 views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
0
votes
1answer
87 views

NP-hardness proof, what is wrong with it?

My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is ...
0
votes
0answers
37 views

What is the global function we are trying to Optimise with Clustering Algorithms?

I am doing some reading (and implementation) of some Clustering Algorithms. First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent ...
3
votes
0answers
50 views

What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
4
votes
0answers
64 views

Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ...
3
votes
1answer
53 views

Optimal way for grouping events

I am creating an event notification system. Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped. All the events ...
4
votes
3answers
87 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
4
votes
1answer
54 views

Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
-1
votes
1answer
60 views

Board cutting problem

To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, ...
1
vote
0answers
72 views

Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably ...
3
votes
0answers
71 views

Formulating Integer Program for passing packages on a cycle

Can't seem to figure out the IP formulation for this. Question Suppose there are $n$ people connected in a circular fashion as demonstrated by the diagram. Individuals need to send packages to each ...
3
votes
2answers
96 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
3
votes
1answer
76 views

Variable Length Encoding of Integers

I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number. Now other schemes are ...
2
votes
1answer
48 views

Progressive discrete multifunction optimization

I have a set of functions $F$. The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|>1000$. (alternatively, they could take a ...
3
votes
1answer
41 views

Does FACTORING have optimal substructure or analog to it?

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily ...
0
votes
1answer
97 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
vote
0answers
38 views

Palstar algorithm Dynamic Programming getting the result [closed]

I recently started to read abour dynamic programming, and I am doing an exercise on it. The problem to solve: Given a String, find the least amount of palindromes it can be split into, and print out ...
1
vote
1answer
32 views

Text search by first order formula

I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates ...
4
votes
1answer
120 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
0
votes
2answers
87 views

Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
7
votes
2answers
65 views

Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements: S = s1 ... sm T = t1 ... tm Semantically both sets are equal, but due to noise ...
0
votes
1answer
57 views

Check constraint under some condition in linear programming

I would like to minimize linear pseudo-boolean function $$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$ subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where $c_1,\dots c_5, ...
4
votes
1answer
88 views

Shortest-depth routing algorithm

This problem came up in a graph network routing context, it can be expressed as follows: Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k ...
1
vote
0answers
47 views

What problem is to the set packing problem, as the hitting set problem to the set cover problem?

Wikipedia says that Set covering is equivalent to the hitting set problem What problem is to the set packing problem, as the hitting set problem is to the set cover problem? Is it that given ...
15
votes
5answers
3k views

Why do low fitness individuals have a chance to survive to the next generation?

I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university). I understand that mutations are based ...
-1
votes
2answers
57 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
vote
1answer
41 views

Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be ...
1
vote
0answers
19 views

Choose m points out of n that form the polytope with the maximum volume in hyperspace

Let's say I have a set $A$ of $n$ points represented by real vectors of length $l$. What type of algorithm would I use to find the subset $B$ of $m$ ($m$ is arbitrary, to be chosen) points that ...
0
votes
1answer
141 views

Floyd–Warshall algorithm on undirected graph

I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm. In case of undirected graphs should I change the assignment statement inside the ...
3
votes
1answer
18 views

What is the significance of the vector dimension in semidefinite programming relaxations?

Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you. So, we first write down an integer quadratic ...
5
votes
0answers
63 views

A matrix rank problem over finite fields

I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here. Let $M|\mathbf w$, where $M$ is a matrix and ...
5
votes
1answer
130 views

Distance k-Dominating Set on a Tree

I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an ...