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

Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
3
votes
2answers
91 views

Solution for a combinatorial minimization problem

Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality ...
3
votes
0answers
157 views

How to compute an optimally cost-effective cache strategy?

I am looking for advice in the following optimization problem. I have a website (system) that receives database updates later returned in queries made to the same system. In order to speed up the ...
1
vote
0answers
601 views

Minimizing concave function with a linear constraint

The problem can be formulated as: $\min f(\textbf{x})=\sum_{i=1}^{n} \prod_{j \in N(i)}(1-F(x_i))$ s.t. $\sum_{i=1}^n x_i \leq B$ $N(i)$ is a set of i. And $F_{x_i}$ can be any function with range ...
2
votes
1answer
83 views

Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
5
votes
1answer
3k views

Seating Chart Optimization

I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized. Each seat has neighbors. A ...
3
votes
1answer
143 views

Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization ...
3
votes
0answers
598 views

Motion planning using second order Bézier curves

I'm trying to find an algorithm for a motion planning problem. I have $N$ points, $P_1$ to $P_N$, in $k$-dimensional cartesian space, defining $N-1$ segments. The problem is about constructing the ...
13
votes
1answer
310 views

Finding maximal factorization of regular languages

Let language $\mathcal{L} \subseteq \Sigma^*$ be regular. A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with $X \cdot Y \subseteq \mathcal{L}$ $X \neq \emptyset \neq Y$...
5
votes
1answer
658 views

Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
2
votes
1answer
36 views

Optimal coverage of a $D$-dimensional grid with small blocks

I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)...
0
votes
1answer
97 views

Algorithm to maximize function of subsets

Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties. What algorithm is most relevant in finding the ...
10
votes
1answer
1k views

Constrainted Optimization Problem in Matrix Entropy

I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $[v_i\,v_i^T]$ where $...
0
votes
1answer
2k views

Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$

Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum. The sub-arrays should not overlap and it can not be ...
7
votes
1answer
2k views

Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
3
votes
1answer
295 views

Is this NP-hard: min-weight n-clique in a complete n-partite graph

I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the ...
5
votes
2answers
1k views

Subset optimization problem

Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. ...
3
votes
1answer
579 views

A variant of job assignment (scheduling) problem with variable time span

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
2
votes
1answer
97 views

Multicommodity circulation formulation

On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
3
votes
0answers
1k views

Deduplication: how to implement content-defined chunking?

I'm writing deduplication program that implements content-defined chunking. Just now i know 3 algorithms to do it (hashing a fixed-size window and selecting hashes < maxuint/N, hashing an order-1 ...
7
votes
0answers
153 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
1answer
1k 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 x ...
4
votes
4answers
587 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, ...
3
votes
0answers
81 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 (minutes/...
2
votes
0answers
82 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
105 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 ...
7
votes
1answer
1k 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 ...
5
votes
1answer
838 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 ...
8
votes
1answer
584 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
55 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 ...
8
votes
2answers
613 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 ...
4
votes
1answer
605 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, \...
14
votes
2answers
14k 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
155 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
447 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
71 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 ...
2
votes
2answers
609 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 ...
6
votes
2answers
7k 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
120 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. ...
11
votes
1answer
7k 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 ...
5
votes
2answers
168 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
3k 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 ...
6
votes
1answer
236 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
88 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
174 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
76 views

Convex optimisation under linear inequality constraints

What are the fastest known algorithms for general convex optimisation under linear inequality constraints?
4
votes
1answer
78 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} \\ \sqrt{u}...
4
votes
1answer
67 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 ...
8
votes
1answer
5k 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
931 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 ...