# Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

1,603 questions
Filter by
Sorted by
Tagged with
2answers
322 views

### Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
2answers
433 views

### Lattice problems

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...). I am curious what work specific to ...
0answers
26 views

### An efficient algorithm for maximizing gain by choosing from a set of options

(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not ) I've got an optimization problem where I need to choose from one of several options to ...
2answers
97 views

### Hospital Resident Matching Algorithm with Incomplete Preferences

Consider a set of doctors $D$ and hospitals $H$ such that each doctor $d \in D$ has a rank ordered strict preference over a subset of hospitals, $H_d \subseteq H$. Similarly, each hospital $h \in H$ ...
1answer
429 views

### Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
0answers
57 views

### Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

I have encountered an interesting problem that I couldn't find any references to solve: Determine the smallest subset of nodes that need to be removed from an undirected graph to make it a tree. ...
1answer
416 views

### What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
1answer
306 views

### Hidden Constants in Complexity of Algorithms

For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (...
0answers
61 views

### Cost of in-place partitioning integer arrays

Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$. Task: Permute the array $a$ in-place so that ...
1answer
123 views

### Given a subset of of the hypercube and an affine transform of it, find the affine map

This is a follow up to this resolved question. Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it $$B=\{Mx + s\mid x\in A\}$$ for some ...
0answers
159 views

### Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
0answers
127 views

### Interpolation of the square of a polynomial

Let $\mathcal{P}^2_n$ be the set of rational polynomials of degree at most $2n$ that are sqares of polynomials, i.e. $\mathcal{P}^2_n$ consists of the set of polynomials of the following form: (a_0 +...
3answers
381 views

### Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
1answer
84 views

### Placing color boxes on a colored image such that color consistency is maximized

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem. Given an image with black background that contains blobs whose ...
1answer
64 views

### What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
1answer
132 views

### Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
3answers
776 views

### Computing sum of sparse polynomials squared in O(n log n) time?

Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient ...
0answers
84 views

### Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
1answer
329 views

0answers
248 views

### Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$. My assumed ...
1answer
642 views

### Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
1answer
63 views

### In external memory, is grouping equal elements easier than sorting?

Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ ...
10answers
2k views

### Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
1answer
80 views

### Longest stack-sortable subsequence

Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$. How fast can this ...
1answer
464 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
5answers
5k views

### What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
1answer
1k views

### Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" ...
0answers
111 views

### Shortest s-t path when is allowed to ignore k weights

Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
0answers
50 views

### Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
0answers
81 views

### Finding 3SUM witness when promised a solution

Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there ...
0answers
97 views

0answers
39 views

### Minimising the maximum distance to the centre of a cluster of points

I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)). I've ...
1answer
125 views

### Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
1answer
236 views

### Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

In the wikipedia article on Time Complexity it is written that: The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
0answers
36 views

### Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
11answers
10k views

### How hard is unshuffling a string?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
1answer
451 views

### Fast sparse boolean matrix chain product

So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually ...