Questions tagged [optimization]
Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
1,253
questions
5
votes
1answer
3k views
Why does Kadane's algorithm solve the maximum sub-array problem?
I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".
it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], ...
5
votes
1answer
234 views
Moving an edge in a weighted tree to maximize longest path length
Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$,...
5
votes
1answer
150 views
Optimization over convex combinations in a circle
Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product
$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$
where $P$ is a point on the circle and $d$ are ...
5
votes
1answer
80 views
Finding minimal and complete test sets for circuits
I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the ...
5
votes
1answer
215 views
Algorithms for logical synthesis of multiple output bits?
Karnaugh maps and the Quine–McCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.
What if I have a situation ...
5
votes
1answer
153 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 (...
5
votes
1answer
594 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 maximum
...
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 ...
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. ...
5
votes
1answer
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 ...
5
votes
2answers
186 views
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.
Now I am learning that a convex optimization problem can ...
5
votes
1answer
110 views
Find a strategy to evade hungry lions on the real line for the longest time
This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.
You are placed on the real line, and there also are $K$ ...
5
votes
2answers
1k views
Finding k-nearest neighbors to a set of nodes in a large graph
Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.
Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ ...
5
votes
1answer
1k views
How can I restructure matrices to have non-zero elements close to the diagonal?
I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members ...
5
votes
1answer
38 views
Find expression with minimal distance to target
I will start of with an informal example and give a more formal problem definition later.
Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and ...
5
votes
1answer
324 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 ...
5
votes
1answer
826 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 ...
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 ...
5
votes
3answers
1k views
Why do we try to maximize Lagrangian in SVMs?
I was learning about support vector machines from MIT OpenCourseWare. I figured it out. I understand why we try to minimize $\frac{1}{2} w^2$. I just did not get why we try to maximize Lagrange ...
5
votes
1answer
247 views
Maximize product of sum of two subset
Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize
$$
\left(\...
5
votes
1answer
94 views
Location Selection Algorithm in Solar Engineering
This is a practical problem in energy generation with heliostats.
We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One ...
5
votes
2answers
191 views
What data structure might this game use?
This question is not about game development or about actual implementation details.
I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
5
votes
1answer
86 views
Coercing a list of nodes into the most probable tree
Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document ...
5
votes
1answer
81 views
Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$
(At the very bottom of this, I will shortly describe the motivation for this question.)
Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ ...
5
votes
2answers
79 views
Global Optimization of a well-defined function with gradient information
I try to minimize the function
$$ f(x_1, …x_n)=\sum\limits_{i}^n-a_i\cos(4(x_i-b_i)) +\sum\limits_{ij}^\text{edge}- \cos(4(x_i-x_j)), \quad
x_i,b_i\in (-\pi, \pi)$$
where $\sum\limits_{ij}^{edge}$ ...
5
votes
2answers
300 views
How can I efficiently find the optimal order to apply special offers to a shopping cart?
Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
5
votes
1answer
2k views
Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers
I have the following problem, which seems to be similar to Set Cover.
We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$).
We're also given a set $S$ of subsets (e.g., $S=\{\{1\...
5
votes
1answer
654 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 ...
5
votes
0answers
89 views
Specific quadratic 0-1 knapsack problem solvable in linear time?
I am interested in a simple variant of the quadratic knapsack problem.
Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
5
votes
0answers
138 views
Can all types of problems be converted to decision problems?
We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well?
Description of the types of problems is ...
5
votes
0answers
132 views
Approximate Weighted Partial Max SAT
Given a Weighted Partial Max SAT problem (WPM-SAT) - are there generally used algorithms or techniques to generate 'approximate' solutions, which are
not necessarily optimal, but found faster than ...
5
votes
0answers
417 views
How to apply ant colony optimization to the TSP but repeating nodes and edges
I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
5
votes
0answers
41 views
Cuttings sticks in congruent equal sharing
You have $n$ congruent sticks (they have the same length). You want to divide them equaly among $m$ friends. To avoid envy, each friend should receive congruent parts, that is, the set of cutted ...
5
votes
2answers
678 views
What is the optimal way to cut B chocolate bars to share equally between N people?
What is the optimal way to cut B chocolate bars to share equally between N people?
Here is an example of different cuts for B = 5 chocolate bars and N = 6 people.
Strategy 1: cut each chocolate bar ...
5
votes
0answers
47 views
Linear functions of matrix exponential
Given a matrix $A$ and a vector $v$, I'm aware there are efficient algorithms for computing $e^Av$, where efficient means significantly faster than computing $e^A$ and multiplying by $v$. For a ...
5
votes
0answers
43 views
Authors of Complementary Slackness
Who were the first researchers to prove the Complementary Slackness condition for linear programming?
I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't ...
5
votes
0answers
153 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 ...
5
votes
0answers
142 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
0answers
39 views
Does it make sense to examine the dual of a feasbility problem?
Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
5
votes
1answer
517 views
Shortest path in a known room for a Roomba
I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
4
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
4answers
552 views
Are there any optimization problems in P whose decision version is hard?
Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
4
votes
2answers
568 views
Suboptimal Solution for a combinatorial problem
I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is ...
4
votes
2answers
306 views
Does local optimization in a genetic algorithm decrease diversity?
I want to create a hybrid genetic algorithm for a project to solve really high dimensional problems (1000+) One of my ideas is to incorporate a local optimization method within GA so each individual ...
4
votes
2answers
367 views
Linear Path Optimization with Two Dependent Variables
Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.
There are two runners on a line that goes from $x=0$ to $x=100$. The two runners ...
4
votes
2answers
3k views
Knight on a chessboard
This is a Hackerrank challenge
$Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ ...
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 ...
4
votes
3answers
947 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 ...
4
votes
1answer
883 views
Minimize number of circles to cover set of points
I'd like to minimize the number of circles $C$ to cover a set of points $P$ in 2D.
There is no fixed radius however each circle must contain exactly $N$ points. The circles may overlap. A point may ...
4
votes
1answer
78 views
Unfeasible linear program becomes feasible if a variable is removed
Apologies, not a computer scientist by trade but I'm playing with linear programming these days.
Let $\{x_i\}$ be $N$ optimization variables with bounds
$$l_i \leq x_i \leq u_i$$
I'm interested in ...
