# Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

1,411 questions
Filter by
Sorted by
Tagged with
384 views

### In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
4k views

### BFGS vs L-BFGS — how different are they really?

I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum ...
105 views

### CNF form of variable assignment problem

There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying ...
283 views

### Are coevolutionary “Free Lunches” really free lunches?

In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-...
4k views

### Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures. The problem is very similar to the ...
168 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 \mathbf{...
2k views

### Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm". The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the ...
192 views

### Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
126 views

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}... 0answers 158 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 ... 2answers 173 views ### Which algorithm can I use to allocate human resources? I have to manage shifts of a variable number of people inside several rooms for a week. Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same ... 2answers 2k views ### Can we create faster sort algorithm than O(N log N) I was thinking that we can create algorithm for sorting that will work faster than$O(N\log N)$Let's say we have given array$A$consisting of$N$integers, where$N = 10^6$. Our task is to sort ... 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\}$... 1answer 4k views ### How to identify when to use Genetic Algorithm/Programming I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem. TSP is basically a permutation/combination problem, and I can understand how GA helps ... 2answers 610 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 ... 2answers 2k views ### Shortest walk through a given subset of edges Given an undirected weighted graph$G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges$e \in E$exactly once? I'd like to know if there is a general approach to this ... 3answers 1k views ### Interpolation Optimization Problem I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - M by N Matrix). Someone marks some pixels as anchors. Now, you need to ... 2answers 1k 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 ... 2answers 122 views ### Optimizing a join where each table has a selection Consider the following query: ... 1answer 406 views ### How to find greatest set intersection of at least a given cardinality? While dealing with a problem, I uncovered this subproblem: Input: A set of sets$S = \{S_1,...,S_r\}$where$\midS_1\cup$...$\cupS_r\mid = n$, as well as a number$k<n$. Output: A ... 2answers 6k views ### How to find spanning tree of a graph that minimizes the maximum edge weight? Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ... 1answer 53 views ### Perpendicular vectors out of a set I stumbled on this problem and I wanna know if there is a better solution. There are$n$3d vectors with$x$,$y$, and$z$components and I wanna find all pairs of perpendicular vectors in this set. ... 1answer 1k 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 ... 3answers 18k views ### Artificial Intelligence: Condition for BFS being optimal It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ... 1answer 81 views ### Selecting vertices in a graph in an order to keep border vertices as few as possible I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white ... 1answer 169 views ### Which potential function does this algorithm minimize or maximize? Considering two sets$A, B$containing some$p$-dimensional points$x \in \mathbb{R}^p$. Let$d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$denote the Euclidean ... 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. ... 2answers 543 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 ... 1answer 3k views ### Fitting different rectangles inside a rectangle I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes. I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate ... 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 ... 1answer 321 views ### How to find several rectangles with minimum area to cover the red cells In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and ... 1answer 245 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 ... 1answer 165 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 ... 2answers 182 views ### Odd cycle transversal and linear programming Suppose we have a graph$G$with$n$vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of$G$, each variable can take value$ā„0$, for each odd cycle of$G$... 1answer 147 views ### Optimal partitioning of n-tuples Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ... 1answer 972 views ### Knapsack with same value I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight ... 1answer 374 views ### Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part I have the following problem in mind. Suppose we have an$n$-dimensional point cloud with$m$points. Each point in the cloud is associated with a value$X_i,1\leq i\leq m$. I would like to use a ... 1answer 599 views ### Finding a certain prefix of a string Let$\Sigma = \{ \sigma_1 , ..., \sigma_t \}$and let$S$be a string from$\Sigma^*$. Denote:$n=|S|$, that is$S$has$n$letters. I'd like to find the shortest prefix$T$of$S$such that$S$is a ... 1answer 86 views ### Time/Space Optimal k-Subset Operator Application - Is this a named problem? I have searched extensively and unsuccessfully for references to a combinatorial problem that arises in my work. I am hoping someone can tell me if this type of problem has a "name" and provably ... 1answer 476 views ### How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points? Let$S \subset \mathbf{R}^3$be a set of points in 3D and let$O=(x_0,y_0,z_0)$be the origin/point of reference. We consider a convex polytope$P$good / interior if:$P$is wholly contained ... 0answers 347 views ### Trying to find a human-usable method to figure out optimal round 1 openings for this game I'm trying to figure out optimal round 1 openings for this game: http://generals.io/. For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that ... 0answers 151 views ### When does greediness guarantee optimality? I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ... 0answers 641 views ### Minimal regular expression that matches a given set of words I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ... 0answers 233 views ### Is greedy minimax permutation rejecting sorting optimal? I sketch an impractical, theoretical comparison sort. Initialize a list of all$n!$permutations of size$n$. For each possible pair of indices$i, j$, count how many permutations would get rejected ... 0answers 741 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-... 4answers 1k views ### Does Thompson's algorithm produce optimal NFAs? I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ... 2answers 7k 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. ... 4answers 618 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 ... 2answers 132 views ### Unknown notation “$e^T\$” in a machine learning paper

I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained ...