general questions about selecting a best element from some set of available alternatives.

learn more… | top users | synonyms

3
votes
1answer
185 views

A weighted sorting problem

Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized. It can be formulated as ...
1
vote
0answers
130 views

What does “no integrality gap” implies?

I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
-2
votes
2answers
203 views

how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?

It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem. ...
2
votes
0answers
68 views

Small area containing large amount of patterns

The problem: I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
3
votes
0answers
186 views

Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables

Integer programing is one of the most narutal optimization tools. As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation. $x_{1}x_{2}x_{3}+$ ...
1
vote
0answers
141 views

What is the shape of cost function of weighted graph matching problem?

According to Umeyama, the weighted graph matching problem can be formulated as $min_P || PA_GP^T - A_H ||$ s.t. $P$ is a permutation matrix. where $A_G$ and $A_H$ are n-by-n matrices If we relax ...
3
votes
0answers
115 views

Existence of complete “asymptotic” optimization problems

Define a function $u:\lbrace 0,1 \rbrace^* \rightarrow \mathbb{R}$ to be an asymptotic optimization problem when the following conditions hold: There is an algorithm $U$ which computes the first $n$ ...
8
votes
2answers
401 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension ...
0
votes
0answers
71 views

Nonmetric TSP and Functional Compleixty Classes

Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method. Is this general TSP a complete problem in some functional complexity classes ? ...
-1
votes
1answer
260 views

Integer compression

I'm looking to devise a scheme for compressing integers which have a known sampled distribution (they might be clustered around a value, say, or have several areas of differing density). So far, I've ...
2
votes
0answers
92 views

Benchmarks for approximation algorithms

I'm working on a Haskell library for approximation algorithms. In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others. Of course, I'd like to benchmark my library ...
1
vote
0answers
163 views

Properties of the subgradient method

The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule $$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and $\alpha(t)$ is a ...
4
votes
1answer
136 views

Splitting line segments with a line

Given is a finite set $S$ of line segments in the plane. I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$. Here ...
5
votes
1answer
219 views

Effective algorithm of searching the “nearest” doubly stochastic matrix

Given a data matrix $D$, is there any effective algorithm to solve the optimization problem $\min_Q || D - Q ||_F$ such that $Qe=e$, $e^TQ=e^T$, and $Q_{i,j} \geq 0 $ $\forall i,j$, where ...
12
votes
1answer
261 views

Numerical stability of Simplex method

The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic. ...
2
votes
1answer
57 views

Covering only one of two types of objects in a cartesian space using minimum number of rectangles

There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the ...
2
votes
1answer
137 views

NP-complete problems related to Minimizing Variance

I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". ...
9
votes
1answer
532 views

Minimum spanning tree over all vertex matchings

I ran into this matching problem for which I am unable to write down a polynomial time algorithm. Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| ...
4
votes
1answer
135 views

Nearly-Eulerian Tours

The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more ...
1
vote
0answers
63 views

Can I apply the constraint while constructing the Lagrangian?

Consider the problem: $\min_X ||XAX^T||_F$ s.t. $X^TX=I$ If A and X are real matrices, the lagrangian will be $tr(XAX^TXA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$ ...
3
votes
1answer
253 views

Stochastic version of a strongly NP-Complete problem

Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ? The problem Tree CVRP(Capacitated Vehicle ...
7
votes
1answer
293 views

NP-hardness of an optimization problem

While studying a problem in algorithmic game theory I got interested in the complexity of the following optimization question: Problem Given: ground set $U = [n] = \{1,\ldots,n\}$ given by $n$, ...
13
votes
1answer
572 views

Exact algorithms for non-convex quadratic programming

This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T ...
14
votes
2answers
845 views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
6
votes
0answers
382 views

Which problems in graph theory can be stated as quadratic programs?

There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ...
5
votes
1answer
228 views

Splitting a graph into minimum number of subpaths

I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There ...
1
vote
0answers
130 views

Trace minimization with an orthogonality constraint

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint: that $X$ is orthogonal. All the matrices have real entries and $A,B$ are ...
2
votes
1answer
843 views

Difference between weak duality and strong duality?

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different: Weak duality: If $\bar{x}$ ...
2
votes
1answer
799 views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
2
votes
1answer
727 views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
8
votes
2answers
635 views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
3
votes
1answer
290 views

Is this multiprocessor scheduling problem with overlaps NP-Hard?

The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
8
votes
1answer
227 views

Maximizing a submodular function of two sets with different size constraints

I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real ...
2
votes
0answers
197 views

Maximizing a convex function where the objective function is separable but the search space is not

The problem statement is Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$ Does this kind of problem structure allow one to use specific strategies to solve the ...
1
vote
1answer
549 views

Vehicle routing problem over Manhattan distances

I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot. Is the following ...
5
votes
1answer
687 views

Implementation that solves minimum set cover

Does anyone know of any tools that solve the approximate minimum set cover problem? I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
1
vote
0answers
234 views

Optimizing along a cube $s=\{0,1\}^n$

I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. ...
4
votes
0answers
655 views

Can the Hungarian method be used with real edge weights?

I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
0
votes
1answer
312 views

To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

I recently watched this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. ...
5
votes
0answers
172 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - ...
3
votes
3answers
255 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
3
votes
1answer
414 views

Maximizing a convex function with linear constraints

I have the following optimization problem: $$ \arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\} \mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq ...
25
votes
3answers
849 views

Rounding to minimise the sum of errors in pairwise distances

What is known about the complexity of the following problem: Given: rational numbers $x_1 < x_2 < \dotso < x_n$. Output: integers $y_1 \le y_2 \le \dotso \le y_n$. Objective: minimise ...
-5
votes
1answer
248 views

Solving a system of linear inequations

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
0
votes
1answer
194 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
0
votes
0answers
88 views

Control optimization for a black box model

Computer science is not my major, hence my question is two folded : how is defined the problem I have (if I can name it, it will be easier for me to look for references) ? what kind algorithm would ...
14
votes
1answer
485 views

Does zero integrality gap imply zero duality gap for certain problems?

We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the ...
0
votes
1answer
234 views

putting objects in buckets — optimization problem

Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let $$ E: \mathcal O \times \mathcal B \to \mathbb{R}_{>= 0} $$ be a function. Is there an ...
4
votes
1answer
199 views

Algorithms for Interval Coloring with Capacities and Demands

We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = ...
8
votes
2answers
342 views

Hardest optimization problems in NC

When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy ...