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

learn more… | top users | synonyms

1
vote
0answers
51 views

Constraint solving for scheduling code with complex unspillable register classes? [migrated]

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
3
votes
0answers
38 views

First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
7
votes
1answer
227 views

Inexact labelled binary tree matching

Does anyone recognise the following problems? Do they have names? Are they hard? If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
2
votes
0answers
53 views

How to prove integrality of LP with not totally unimodular matrix

I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for ...
1
vote
1answer
65 views

On a Linearization of the Quadratic Assignment Problem

The Quadratic Assignment Problem formulated as an integer program: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n ...
0
votes
0answers
76 views

Binary Search for optimisation problems

This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there ...
1
vote
0answers
90 views

Empty sudoku and NP-completeness [closed]

My question is straightforward: Is an empty sudoku grid (not partially completed) still NP-complete?
10
votes
2answers
227 views

Easy to optimize but hard to evaluate

Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution? For the sake of ...
3
votes
0answers
45 views

Quantum annealing or adiabatic quantum optimization with continuous optimization problems

How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
1
vote
0answers
123 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
0
votes
0answers
37 views

Integer sublattice of unit hyperplane

Consider the polytope $\mathcal{H}=\{(x_1,\dots,x_n)| \ell_i\leq x_i\leq u_i\; i=1,\dots,n; \sum_{i=1}^n x_i=1\}$ where $\ell_i,u_i\in [0,1]$ for $i=1,\dots,n$. It is easy to see that $\mathcal{H}$ ...
3
votes
0answers
57 views

Pathfinding search over a space with known changing costs

I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time. More specifically, the danger values represent bad weather, ...
1
vote
0answers
37 views

How to compute the basis

Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and $W= ...
6
votes
0answers
84 views

SVM - running time for detecting if data is linearly separable?

If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
1
vote
0answers
19 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
0
votes
0answers
141 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
4
votes
1answer
67 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
4
votes
1answer
168 views

What do you call the join of two optimization problems?

I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with ...
4
votes
1answer
103 views

Minimum weight matching in general graphs with additional input specifying the number of matched edges

We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of ...
3
votes
2answers
751 views

Finding the two shortest paths while minimizing the number of nearby/common edges

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary. Consider the following variant: ...
5
votes
0answers
114 views

Completing a matrix (over the reals) to be singular

Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
4
votes
2answers
208 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
3
votes
0answers
93 views

NP-hardness of a quadratic programming problem

Motivated by the mean-variance optimization, I came up with the following question: Given $n$ integers $a_1, \cdots, a_n$; $n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$ $n$ upper bounds ...
0
votes
2answers
101 views

Finding a set of hubs in a graph

Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source ...
1
vote
1answer
157 views

NP-Hardness for an optimization problem

I want to prove that the following optimization problem is NP-Hard. max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$ subject to $x_j \in ...
0
votes
1answer
94 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
11
votes
0answers
241 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
0
votes
0answers
200 views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
5
votes
1answer
105 views

Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution. For instance, ...
2
votes
0answers
125 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
2
votes
0answers
100 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
0
votes
0answers
62 views

Preventing cycling in the simplex method

In Matoušek and Gärtner's excellent book, Understanding and Using Linear Programming, they discuss various pivot rules and in particular ones designed specifically to avoid cycling. Unfortunately, ...
2
votes
0answers
99 views

Is minimizing sum of distances hard?

The Problem Given a set of $n$ points $S = \{v_1, v_2, \cdots, v_n\} \subset \Re^d$, find a unit vector $s \in \Re^d$ such that $s$ minimizes $$ \sum_{i=1}^{n}\sqrt{\|v_i\|^2 - \langle v_i, s ...
13
votes
1answer
233 views

Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$, all in binary. Output: A $k$th smallest ...
9
votes
1answer
327 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
25
votes
5answers
4k views

Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
10
votes
1answer
361 views

Numerical precision in sum-of-squares method?

I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ...
8
votes
2answers
134 views

Reordering data to optimize for compression?

Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I ...
5
votes
0answers
95 views

Optimizing over symmetric polynomials [closed]

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 ...
4
votes
2answers
390 views

Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
2
votes
1answer
111 views

Is there a name for this Assignment definition

The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks. Now consider the following generalization: Instead of specifying a cost of a single agent-task ...
2
votes
0answers
108 views

What is the most “unbalanced” vector between two given vectors of numbers?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on ...
0
votes
0answers
131 views

Steiner Tree and minimum spanning tree

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
2
votes
1answer
131 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
0
votes
0answers
71 views

Approximation Algorithm for TSP-like problem

Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with ...
1
vote
0answers
96 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
1
vote
1answer
94 views

direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

Is there a direct conversion between gradient descent ([1], Alg 1 ) and any of the following algorithms? 1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm 2) ...
1
vote
2answers
125 views

Finding the paths through a graph that reuse as many of the nodes as possible

I'm implementing an encryption algorithm which does a bunch xor operations to mix up the columns. Because I want to find the lower bound of the number of ...
17
votes
2answers
194 views

Minimal cumulative set sum

Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$. Are there known algorithms ...
14
votes
1answer
168 views

What is the state of the art in cache algorithm theory?

I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a ...