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
4
votes
0answers
450 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
611 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
124 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
169 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
949 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 ...
4
votes
2answers
1k 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
77 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 ...
1
vote
0answers
525 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 ...
3
votes
2answers
2k 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 ...
10
votes
1answer
576 views

Maximizing a convex function with a linear constraint

$$\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b}$$ where $$f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}},$$ $\mathbf{x} = [...
5
votes
2answers
6k views

The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
4
votes
1answer
1k 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 ...
2
votes
1answer
537 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
32 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
590 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
117 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 ...
7
votes
2answers
250 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 ...
20
votes
1answer
2k 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 ...
8
votes
0answers
609 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 ...
9
votes
1answer
188 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 ...
0
votes
1answer
2k 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
120 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 ...
6
votes
1answer
164 views

Can all packing/covering problems be rephrased as set packing/covering problems?

Can all packing problems be rephrased as set packing problems? Can all covering problems be rephrased as set covering problems? In other words, I was wondering if set packing/covering problems are ...
5
votes
3answers
2k views

Min cost max flow in bipartite run time

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost). For the sake ...
6
votes
2answers
960 views

A variant of the Assignment Problem

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
4
votes
1answer
173 views

Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
3
votes
0answers
47 views

A variant of the assignment problem (?) [duplicate]

Possible Duplicate: A variant of the Assignment Problem (Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.) In my variant of the problem I ...
4
votes
1answer
185 views

Formulating a linear program s.t. only extreme point solutions are found

If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ...
2
votes
1answer
92 views

What is a good resource to learn about oriented matroids in the context of digraphs and optimization?

I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good ...
1
vote
0answers
70 views

How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?

In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
2
votes
1answer
207 views

How to reduce MaxUNSAT to MaxSAT?

Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ? When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is ...
3
votes
2answers
243 views

Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem

I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls ...
6
votes
0answers
717 views

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a non-...
8
votes
2answers
1k views

Known facets of the Travelling Salesman Problem polytope

For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of ...
1
vote
1answer
50 views

Produce decision version of the problem

An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?
15
votes
4answers
7k views

Given a set of sets, find the smallest set(s) containing at least one element from each set

Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...
11
votes
0answers
720 views

Fast algorithm for max-convolution with concave functions?

I'm interested in a discrete max-convolution problem, which is to compute $$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$ for all values $c=0, \ldots, C$, where $x=(...
5
votes
2answers
3k views

Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
4
votes
3answers
1k views

Assign m agents to N points by minimizing the total distance

Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final ...