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
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
154 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
144 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
595 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
687 views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
4
votes
2answers
4k views

Why can't we round results of linear programming to get integer programming?

If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed? If linear programming suggests we can afford only $3.7$ workers, then ...
4
votes
2answers
624 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
96 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 ...
4
votes
2answers
321 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
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 ...
4
votes
1answer
1k 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
532 views

Can integer linear programs have non-integer OPT solutions?

Why is it that every integer linear program has optimal solutions that are integers? At least in online text books, they are always integers. Can solutions of ILPs only be integers?
4
votes
1answer
498 views

Project to nearest point in convex polytope

Is there a reasonably efficient algorithm for the following task? Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$ Find: a point $y \in \mathcal{C}$ that is ...
4
votes
1answer
802 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
4
votes
1answer
79 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 ...
4
votes
2answers
335 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
4
votes
2answers
74 views

Finding the number of ways to partition $\{1,…,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

I am trying to think of how to optimize the following problem: Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
4
votes
1answer
570 views

Definition of $\alpha$-approximation

I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation. Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if ...
4
votes
1answer
179 views

Distributing resources for maximum gain

This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it. Suppose there is a collection of shared resources, and a collection of possible ...
4
votes
2answers
150 views

Discrete assignment problem with penalties

I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods. It's an single agent problem where we have to ...
4
votes
1answer
1k views

Closed form solution for optimization problem

Consider the problem of finding the real-valued matrix $C$ so that $$\|S-AC\|_F^2\qquad(1)$$ is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has ...
4
votes
1answer
363 views

Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$. I would like to select a ...
4
votes
1answer
3k views

Using dynamic programming to maximize work done

Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ ...
4
votes
1answer
906 views

Minimizing inversions in an array with a single swap

This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased: Given a permutation $a$ of integers from $1$ to $N$, how can I minimize the number of inversions by a single swap ...
4
votes
2answers
5k views

What TSP variant doesn't return to start point?

For my case I have starting point and several cities. I want the shortest route to visit all cities without returning starting point. I have read several TSP algorithm and all include the return a ...
4
votes
4answers
614 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, ...
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
2answers
81 views

Largest weight-limited connected subgraph: NP-complete?

When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of ...
4
votes
2answers
68 views

Among $k$ unit vectors, find odd set with sum length less than 1

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
4
votes
2answers
257 views

Auction where each bidder bids on a bundle of items

Is there some optimal solution in an auction where each bidder bids on a bundle of items?
4
votes
1answer
238 views

Algorithm to enclose a 2D-gridbased-room efficient

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort. Here a little Example: In this example black squares are not passable, ...
4
votes
1answer
2k views

Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum $k$-cut problem asks for a minimum weight $k$-cut. For $k=2$ this problem is P. Vazirani in ...
4
votes
1answer
286 views

Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
4
votes
1answer
166 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \...
4
votes
2answers
328 views

Minimizing Cost by minimizing delay

There is a complete binary tree with its leaves as components of some system The values from one node to another gives propagation time for a signal to propagate from one junction to another For the ...
4
votes
1answer
84 views

Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
4
votes
1answer
162 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
1answer
130 views

Need help understanding this optimization problem on graphs

Has anyone seen this problem before? It's suppose to be NP-complete. We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ ...
4
votes
1answer
174 views

How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'...
4
votes
1answer
65 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
4
votes
2answers
62 views

Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?

I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 ...
4
votes
1answer
639 views

Algorithm(s) for creating balanced 5-a-side teams?

I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than ...
4
votes
2answers
2k views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
4
votes
1answer
115 views

What is the global function we are trying to Optimise with Clustering Algorithms?

I am doing some reading (and implementation) of some Clustering Algorithms. First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent ...
4
votes
1answer
133 views

What is the significance of the vector dimension in semidefinite programming relaxations?

Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you. So, we first write down an integer quadratic ...
4
votes
2answers
180 views

Genetic algorithm: What is the expected number of strings that are explored?

My question concerns genetic algorithm searching along bit strings. Given: $N$ = population size $l$ = length of bit strings $p_c$ = probability that a single crossover occur (double crossover never ...

1
3 4
5
6 7
28