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

learn more… | top users | synonyms

1
vote
0answers
185 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
3
votes
1answer
131 views

Complexity class for Optimization problems over #P functions

Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e: $$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$ where $f\in\# ...
1
vote
0answers
80 views

Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?

Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so ...
0
votes
0answers
108 views

Continuous version of rod cutting

This is an attempt to extend an idea from Computer Science.. the dynamic programming based solution of the rod cutting problem (given a rod of an integral length and an array of prices for each ...
-1
votes
1answer
136 views

Is l1-norm works better that l2-norm in minimization using projection method?

Given a vector of errors $e(x)$ obtained by variable $x$ In the following problem : $min_x || e(x) ||$ Besides the robustness, consider only convergence speed, is it l1 norm works better than l2 ...
0
votes
1answer
111 views

Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
4
votes
1answer
154 views

Minimize in polynomial time a super-additive increasing function under linear constraints?

I am looking for references whether this problem can be doable in polynomial time (or other known approximation results): Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$), $$ ...
2
votes
0answers
115 views

Proving greedy algorithm is optimal for a scheduling problem

First, the problem discription: For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
2
votes
0answers
87 views

Optimal additive basis for decomposing/partitioning an integer as a sum of two integers

I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$. A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ ...
11
votes
0answers
161 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
1
vote
1answer
155 views

Ising spin vs Pauli spin matrices [closed]

Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this ...
3
votes
3answers
564 views

Maximize quadratic function subject to linear constraints

Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$? This paper seems to come close to answering "no." They show it is ...
0
votes
1answer
2k views

Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
3
votes
0answers
67 views

Closest Vector Problem with sparse basis and target vector

The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
10
votes
0answers
163 views

Expected length of a self-avoiding random walk

We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists. ...
1
vote
0answers
260 views

Confusion related to L1 and L2 svm [closed]

I have this confusion related to L1 and L2 svm. It is given in this paper that The dual problem is given by $$ min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha $$ subject to $$ 0 <= \alpha_i ...
1
vote
0answers
92 views

Poly-time Algorithm for Non-Linear Optimization

As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
2
votes
2answers
249 views

Undecidability of program optimization

A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that: On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is ...
3
votes
1answer
186 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
135 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
229 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
69 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
197 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
144 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
120 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
448 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
84 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
289 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
95 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
171 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
138 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
241 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
278 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
139 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
543 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
136 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
64 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
269 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
306 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
611 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
889 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
405 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
247 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
135 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
1k 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
867 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
844 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
707 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
297 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 ...