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

learn more… | top users | synonyms

1
vote
0answers
159 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
134 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
205 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
251 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
56 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
131 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
517 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
248 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
283 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$, ...
11
votes
1answer
323 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 ...
13
votes
2answers
795 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
351 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
211 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
126 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
698 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
739 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
624 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' ...
7
votes
2answers
597 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
273 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
226 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
192 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
510 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
602 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
611 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
303 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
163 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
244 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
388 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
809 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
239 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
188 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
456 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
216 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
198 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
339 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 ...
5
votes
1answer
241 views

Is it possible to include an optimization algorithm's own running time in the cost?

Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize. Now, we have an algorithm $A$ that takes as input $P, a, ...
0
votes
1answer
119 views

Name of the problem to find the maximum number of characters covered by a set of strings

I am interested in the following problem. One has two collections $Q$ and $T$ of strings, and a set $A$ of alignments of strings in $Q$ to strings in $T$. I want to find a subset $A'$ of $A$ that (i) ...
10
votes
3answers
292 views

min hitting set of every base of a matroid

We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, ...
0
votes
1answer
187 views

PH and Optimization Problems

If we have a machine which can solve any problem in the second level of PH, can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or ...
3
votes
0answers
313 views

Minimal context-free Grammar for a special one-letter Language

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given: $$ L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\} $$ Find and ...
9
votes
2answers
315 views

A variation on discrepancy involving random graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
14
votes
2answers
340 views

Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
1
vote
1answer
535 views

Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
3
votes
1answer
226 views

Minimum length walk from s to t covering a subset of vertices

I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), ...
5
votes
1answer
922 views

Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized. The greedy ...
0
votes
1answer
712 views

Linear Programming with Modulo Linear Constraints

Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as: find feasible point s.t. $\min \sum_{ij}v_{ij}$ for all $(i,j)$ in $E$ $z_{ij} \le (c_i - c_j) \bmod k$ (i) $z_{ij} \le ...