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

5
votes
1answer
35 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
0
votes
1answer
25 views

Why can no task have a utilization rate greater than one?

Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$ Then $U$ must be less or equal to $1$ for the task to be schedulable ...
0
votes
0answers
25 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, ...
5
votes
1answer
161 views

Solving road trip problem in linear time

Consider the following problem: You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between ...
9
votes
1answer
1k views

What is the optimal solution of the 1962 Procter and Gamble's TSP Contest?

In 1962, you could win a prize of \$ 10 000 (about \$ 80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities. ...
0
votes
0answers
36 views

Designing a scheduling algorithm

I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario. I have customers who have selected how many hours they want ...
1
vote
1answer
35 views

How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

How can TSP be an NP-optimization problem ? The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and ...
1
vote
1answer
50 views

Construction of fair teams

let's say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team. Each team consists of two players. One player is ...
0
votes
1answer
34 views

Lower bound the difference between distinct values of a function over a discrete domain?

I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose ...
17
votes
3answers
1k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
2
votes
1answer
47 views

The maximum number of statements that could be true at the same time

I've come across a programming question. I can't solve it but I can write the question in mathematical form as follow: Receive k equations,and for each equation receive 3 variables a, b, and c in ...
-2
votes
0answers
58 views

Variation of Max Flow Problem

The PCMF problem is similar to the maximum flow problem, but has these features: each vertex $u\in V − \{s, t\}$ has conservation factors $a_u, b_u \in \mathbb R$ (set of real numbers) with $0 ≤ a_u ...
-1
votes
1answer
74 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? ...
2
votes
1answer
21 views

Monotone Frameworks: Transfer functions for flow edges instead of labels

So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$. The goal ...
2
votes
0answers
30 views

A fast algorithm for a simple multi-objective minimization?

I have a set $S$ of $n$ (arbitrary) integers which I want to partition into subsets $S_1, \dots, S_k$, each of size $n/k$ (you can assume that $k$ divides $n$). Let $A$ be the arithmetic mean of ...
6
votes
1answer
54 views

Mathematical optimization on a noisy function

Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x ...
3
votes
1answer
65 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
7
votes
1answer
135 views

Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace ...
0
votes
0answers
13 views

What do we schedule in JSSP? [duplicate]

I am working (for my personal knowledge) on the Job Shop Scheduling Problem, after doing some research on this topic, I still cannot figure out what do we schedule ? Do we schedule jobs or do we ...
5
votes
1answer
112 views

Fast solution for a combinatorial maximizaton problem

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 ...
-1
votes
1answer
17 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
vote
1answer
32 views

Integer Programming - packing wolves and sheep

I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and ...
0
votes
1answer
33 views

What is the advantage of Day-Stout-Warren algorithm for balancing BST?

While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time. In my opinion I can ...
1
vote
0answers
23 views

C++: Minimization Using Levenberg Marquardt to Solve for Two Variables [closed]

I am trying to solve this equation using C++: X and Y are both given sets of data. X = [x1, x2, ... , xn], Y = [y1, y2, ... , yn] a is a given integer. The goal is to find a pair z and k that ...
3
votes
1answer
25 views

Finding set of disjoint sets with additional value optimization

I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties: Sum of all $v$'s is ...
1
vote
0answers
15 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
3
votes
1answer
42 views

How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves ...
9
votes
2answers
112 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
1
vote
2answers
31 views

Litterature on network-flow (optimization) approximation algorithms

I've been searching on litterature about approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree. However, been looking in several well-known ...
2
votes
1answer
36 views

Spandex knapsack?

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
2
votes
0answers
31 views

Optimize sequence when item costs are interdependent

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there. ...
2
votes
0answers
67 views

Optimal wagering to minimize expected time to reach a target payoff

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
1
vote
1answer
63 views

Are there some real-world optimization problems with very cheap objective functions?

Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a ...
1
vote
1answer
100 views

Find a quarrel-free seating order with a greedy algorithm [duplicate]

I'm revising for an Algorithms exam and looking at a sample question it says : A group of n teenagers $t_1, \dots, t_n$ are to sit in a single row of n chairs watching a particulary boring comedy ...
1
vote
1answer
17 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
6
votes
1answer
118 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
5
votes
3answers
212 views

How to choose the maximum number of nodes (with constraints) from a graph

Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. A positive integer $x$ is given and you want to choose at ...
15
votes
3answers
252 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
0
votes
2answers
80 views

Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
0
votes
2answers
50 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function ...
2
votes
1answer
51 views

How should I choose the neighborhood structure for simulated annealing for my problem?

There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C_i \subseteq \{1,\ldots,m\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a ...
0
votes
0answers
16 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 ...
3
votes
1answer
84 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal 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 ...
1
vote
0answers
62 views

Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
3
votes
2answers
57 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
1
vote
1answer
111 views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
0
votes
0answers
48 views

How can I solve this constrained assignment problem?

The assignment problem is defined as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on ...
1
vote
1answer
70 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
1answer
67 views

The most efficient way of finding/storing neighbourhood info during octree creation

Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box ...
1
vote
1answer
32 views

Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...