# Questions tagged [optimization]

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

1,399 questions
Filter by
Sorted by
Tagged with
177k views

### What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
26k views

### Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
9k views

2k views

### Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
1k views

### How fundamental are matroids and greedoids in algorithm design?

Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
2k views

### Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
Consider the following algorithmic task: Input: a positive integer $n$, along with its prime factorization Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $... 4answers 1k views ### How to use a greedy algorithm to find the non-decreasing sequence closest to the given one? You are given n integers$a_1, \ldots, a_n$all between$0$and$l$. Under each integer$a_i$you should write an integer$b_i$between$0$and$l$with the requirement that the$b_i$'s form a non-... 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 ... 6answers 14k views ### How is Dynamic programming different from Brute force I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. ... 3answers 421 views ### How many cookies in the cookie box? — Tiling stars With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ... 13answers 10k views ### Why do we need full-fledged workstations running massive OSes with massive software? I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of ... 2answers 2k views ### Largest sum divisible by n I asked this question on StackOverflow, but I think here is a more appropriate place. This is a problem from Introduction to algorithms course: You have an array$a$with$n$positive integers (... 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 ... 2answers 15k 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 ... 1answer 2k views ### What is the optimal solution of the 1962 Procter and Gamble's TSP Contest? In 1962, you could win a prize of \$ 10 000 (about \$80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities. http://www.math.uwaterloo.ca/... 1answer 332 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$... 1answer 2k views ### Analyzing a modified version of the card-game “War” A simple game usually played by children, the game of War is played by two people using a standard deck of 52 playing cards. Initially, the deck is shuffled and all cards are dealt two the two players,... 2answers 1k views ### MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard? What is the complexity of$\text{MIN-2-XOR-SAT}$and$\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{... 2answers 683 views ### Matrix chain multiplication and exponentiation If I have two matrices A and B, of dimensions 1000\times2 and 2\times1000, respectively, and want to compute (AB)^{5000}, it's more efficient to first rewrite the expression as A(BA)^{4999}... 5answers 1k views ### How to find the maximal set of elements S of an array such that every element in S is greater than or equal to the cardinality of S? I have an algorithmic problem. Given an array (or a set) T of n nonnegative integers. Find the maximal set S of T such that for all a\in S, a\geqslant |S|. For example: If T=[1, 3, 4, ... 3answers 3k views ### Optimal strategy for an abstract game I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number A_0. (E.g. A_0 = 1234.) ... 1answer 5k views ### Choosing a subset to maximize the minimum distance between points I have a set of points C, and I have the distance between each point D(P_i,P_j). These distances are euclidean but the points are actually in a feature space. From the C points I want to choose ... 1answer 383 views ### Is packing a bag of presents easier for Rupert than Santa? Or: Do we need Rupert in order to get presents at all? Routing issues aside, Santa faces the following problem (many, many times over): Given a bag with capacity¹ C and a set of presents \{p_1, \... 0answers 597 views ### Optimal meeting point in directed graph Let G(V, E) be a edge-weighted directed connected graph and v_1, \dots, v_n \in V be some vertices. Let d(a, b) denote the length of the shortest path from a to b, for a,b \in V. I need ... 2answers 440 views ### Is this special case of a scheduling problem solvable in linear time? Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,... 3answers 2k views ### Algorithm to match numbers with minimum number of moves This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far. Given a series of numbers, e.g. ... 2answers 4k views ### What is a bicriteria approximation algorithm? What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization? This is where I came across it: cis.upenn.... 5answers 11k views ### Data Science vs Operations Research The general question, as the title suggests, is: What is the difference between DS and OR/optimization. On a conceptual level I understand that DS tries to extract knowledge from the available data ... 2answers 2k views ### Minimize the maximum component of a sum of vectors I'd like to learn something about this optimization problem: For given non-negative whole numbers a_{i,j,k}, find a function f minimizing the expression$$\max_k \sum_i a_{i,f(i),k}$$An example ... 4answers 1k views ### Finding exact corner solutions to linear programming using interior point methods The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ... 1answer 583 views ### A continuous optimization problem that reduces to TSP Suppose I am given a finite set of points p_1,p_2,..p_n in the plane, and asked to draw a twice-differentiable curve C(P) through the p_i's, such that its perimeter is as small as possible. ... 3answers 1k views ### Algorithms for minimizing Moore automata Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ... 1answer 13k views ### Variant of the knapsack problem How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant p ? This is the same problem (max weight of ... 3answers 153 views ### Minimum circles to cover a set of points and avoid another set of points Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in ... 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 ... 1answer 1k views ### Distribute objects in a cube so that they have maximum distance between each other I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure ... 1answer 379 views ### How fast can we compute the size of maximum matching in an unweighted bipartite graph? Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ... 0answers 1k views ### Alternative to Bloom filter for extreme parameters A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ... 0answers 743 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=(... 4answers 1k views ### Cutting equal sticks from different sticks You have n sticks of arbitrary lengths, not necessarily integral. By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get k<n sticks such that: ... 3answers 686 views ### Wiring Length Minimization My Problem is like this: I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where ... 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 ... 1answer 654 views ### Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly? I want to produce k shortest path (k would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ... 2answers 353 views ### How do I classify my emulator input optimization problem, and with which algorithm should I approach it? Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ... 1answer 612 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} = [...
Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value \$x \...