Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
4
votes
0answers
32 views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
0
votes
0answers
38 views
Algorithm to solve job assignment problem
Can someone suggest an algorithm to solve job assignment problem with condition?
With condition means that some jobs cannot be done by some workers. For example table as shown below:
In this table ...
3
votes
3answers
35 views
Using a computer algebra system to optimize mathematical expressions
This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, ...
1
vote
0answers
25 views
What is an appropriate global optimization technique for a noisy and expensive function?
I have a function which takes 22 real-valued parameters as input that returns a real value. The function is reasonably fast for low return values (ms/seconds/minutes), but takes much longer ...
3
votes
0answers
52 views
Issues with an optimization problem
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
1
vote
2answers
63 views
Finding the required value of an algebric expression
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
0
votes
0answers
17 views
Interval Scheduling Optimization type of Problem, optimal order of manufacture
We wish to manufacture n distinct hardware items. Each item needs to go through 3 stages of processing. The first stage called design can only be performed by our master designer who works by starting ...
5
votes
1answer
100 views
NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.
Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
3
votes
0answers
40 views
Decision vs Optimization version for Problems of two Parameters
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.
Now the corresponding decision problem $foo(M)$ would be: Is there a ...
7
votes
1answer
94 views
Finding the largest 3-clique-free induced subgraph
Consider this problem:
Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:
$G'$ is an induced subgraph of $G$
$G'$ has no 3-cliques
$|V'|$ is maximal
So the ...
2
votes
1answer
29 views
What is the name of the optimization that removes self eliminating multiplication-division statements?
I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it.
Given an integer x, not known at optimization time, a known constant ...
5
votes
1answer
37 views
Finding a set of maximally different solutions using linear programming or other optimization technique
Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is ...
3
votes
1answer
31 views
Minimizing a multivariate polynomial over the hyper-cube is NP-Hard
In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, ...
6
votes
2answers
67 views
Initial temperature in simulated annealing algorithm
I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.
Is there any way ...
4
votes
1answer
45 views
Prize collecting steiner tree
I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
4
votes
0answers
27 views
Variation of interval scheduling algorithm with several job categories, only one from each can be used
I have a problem similar to the interval scheduling algorithm. The differences are:
The jobs have the same length.
There are several categories of jobs and only one job from each category can be ...
2
votes
0answers
18 views
Throughput measure
I have to implement a limitation algorithm in order to avoid to reach a throughput limit imposed by the service I'm interacting with.
The limit is specified as «N request over 1 day» where N is of ...
1
vote
2answers
75 views
Polynomial time reductions using binary search
There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a ...
4
votes
1answer
112 views
Algorithm to return largest subset of non-intersecting intervals
I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.
i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...
2
votes
0answers
24 views
Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy? [duplicate]
I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. ...
7
votes
1answer
96 views
What algorithm would compute the maximum choices from two sets?
Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two ...
4
votes
2answers
71 views
Constraint violation and efficiency in search
It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:
Start with a feasible solution and expand search until constraints ...
1
vote
1answer
50 views
Interval Scheduling Problem with more than One Resource
Consider the interval scheduling problem, see also here.
In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...
5
votes
1answer
113 views
Optimal partition of a set of pairs
Suppose we have a set $S = \{(a_1,b_1),...,(a_n,b_n)\}$ where $a_i < m$, $b_i = m-a_i$, $m \in \mathbb{Z}^{+}$, $m>2$ and $n$ is an even number greater than $3$. What is the most efficient ...
2
votes
1answer
45 views
Algorithm for finding optimal branch points
I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd ...
2
votes
0answers
39 views
Experimental Survey on Different Heuristics for Knapsack Problem
I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
3
votes
0answers
62 views
Convex optimisation under linear inequality constraints
What are the fastest known algorithms for general convex optimisation under linear inequality constraints?
4
votes
1answer
69 views
Can one have a condition like this in semidefinite programming?
Is it possible to have the following condition in a semidefinite programming as a constraint?
$
M=
\left[ {\begin{array}{cc}
a & \sqrt{u} \\
...
2
votes
0answers
37 views
Congestion Game with Varying Price
I molded my problem as the following game (it is a congestion game with varying price):
$N$ players share resources $E$,
$S_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is ...
1
vote
0answers
80 views
Quality LISP/Scheme compilers to compete with C/C++
Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin?
In my testing, I've found that the ...
3
votes
0answers
74 views
Dynamic Knapsack Problem - Algorithms and References
I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
3
votes
2answers
74 views
Convergence of Simulated Annealing Based Algorithms
I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge ...
3
votes
2answers
63 views
Algorithms to prioritize equipment renewals
I am looking for algorithms to prioritize equipment renewals.
Input: (years since last renewal, cost of renewal, importance of renewal).
Output: An ordering of the equipment according to which it ...
0
votes
0answers
51 views
Streaming Knapsack Problem
I want to implement efficiently "streaming Knapsack" problem in java.
The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,...
The question ...
2
votes
1answer
143 views
Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler
Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are ...
1
vote
0answers
38 views
Arora's PTAS for the k-MST-Problem
I've just read Arora's paper "Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems". On page 8 Arora says that the dynamic programming procedure can be changed to get a ...
8
votes
1answer
86 views
Maximizing a convex function with a linear constraint
The problem is
$$\max f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$
where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$,
$\mathbf{x} = ...
4
votes
1answer
181 views
Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:
The element 1 is in position 1, and element N must be ...
1
vote
0answers
80 views
Proving that no deterministic algorithm can be better than a 3-approximation
There are three popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the ...
1
vote
1answer
71 views
Using Clique decision to solve Clique optimization
How can you perform the clique decision algorithm fewer than $ O(n) $ times to solve clique optimization?
I'm not sure if my approach is right but this is my thought process: you would pick vertices ...
2
votes
0answers
23 views
Inferences about Branching in TSP algorithm
I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was ...
5
votes
2answers
119 views
Randomized Rounding of Solutions to Linear Programs
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
2
votes
2answers
49 views
Optimization-factoring $\le_p$ Decision-factoring
Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$
Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$
How can I ...
6
votes
2answers
100 views
Are monoids useful in optimization?
Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example).
There is ...
9
votes
0answers
167 views
How to pack polygons inside another polygon?
I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.
I can scan the leather sheets ...
7
votes
0answers
350 views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
6
votes
0answers
47 views
Fixed-length decision-tree-like feature selection to minimize average search performance
I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear ...
-2
votes
1answer
164 views
Dijskstra's algorithm, maximum flow
For directed graph $(G=(V, E),s,t,{Ce})$ in which we want to maximize max flow. All edge capacities are at least one. Define the capacity of an $s \to t$ path to be the smallest capacities of ...
-1
votes
1answer
196 views
Integer LP formulation and the existence of a solution
A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will ...
1
vote
0answers
90 views
Is it possible to analyse computation?
Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation.
So you have a ...
