AlgOrEsEArch

AlgOrEsEArch

Founded by Adrian Dumitrescu: a computer scientist and mathematician with expertise in the fields of theory of algorithms, combinatorics, and discrete and computational geometry. Adrian Dumitrescu holds a PhD in Computer Science from Rutgers University and is an author of about 250 academic papers and a recent book on algorithmic problems and exercises. More details can be found here.

Email us your proposal at contact@algoresearch.org







Books

  1. Adrian Dumitrescu and Ke Chen, The Ape Book: Algorithmic Problems and Exercises, ISBN: 9798674163009, August 2020. (Available at amazon.com)


Papers

  1. Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot, On convex polygons in Cartesian products, Journal of Computational Geometry, 11(2), 2020, 205-233. Preprint available on arXiv.

  2. Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth, On the stretch factor of polygonal chains, SIAM Journal on Discrete Mathematics, to appear.

  3. Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth, Sparse hop spanners for unit disk graphs, Computational Geometry: Theory and Applications, to appear. Preprint available on arXiv.

  4. Adrian Dumitrescu, Finding triangles or independent sets, manuscript, 2021. Preprint available on arXiv.

  5. Adrian Dumitrescu and Josef Tkadlec, Piercing all translates of a set of axis-parallel rectangles, Proceedings of the 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), Ottawa, Canada, July 2021, Vol. 12757 of LNCS, pp. 295-309, Springer, 2021. Preprint available on arXiv.

Open Problems

Topics: exact algorithms, approximation algorithms, randomized algorithms, discrete and computational geometry, etc. Each problem is labeled by the proposer and/or the owner of the current best result. For brevity in what follows we write "argue that none exists" instead of "argue that none exists within a reasonable framework."

  • [Paterson:] Conjecture. The worst-case number of comparisons required to find the median of \(n\) elements is asymptotic to \(n \log_{4/3} 2 \sim 2.4094\ldots n.\)  See also here.

  • [Kislitsyn:] "\( 1/3 \) - \( 2/3 \) Conjecture"  For every poset that is not a chain, there is some pair of elements \( x \) and \( y \) so that \( x \) appears above \( y \) in a random linear extension of the poset at least \( 1/3 \) of the time and at most \( 2/3 \) of the time.  See also here.

  • [Berlekamp:] Can \(X + Y\) sorting be done in \(o(n^2 \log{n})\) time?  See also here.

  • [Woeginger:] In the SUBSET-SUM problem, given \(n\) positive integers \(a_1,\ldots,a_n\) and a target sum \(t\), the problem is to decide whether there exists some subset of the \(a_i\) that add up to \(t\). (SUBSET-SUM is known to be NP-hard.)  See also here.
    (a) Construct an \(O(1.4^n)\)-time algorithm for SUBSET-SUM or argue that none exists.
    (b) Construct an \(O(1.99^n)\)-time and polynomial space algorithm for SUBSET-SUM or argue that none exists.

  • [Woeginger:] The standard CLIQUE problem asks to find a clique of maximum size in a given graph \(G=(V,E)\). Let \(|V|=n, |E|=m\).  See also here.
    Construct an exact algorithm for CLIQUE with time complexity \(O(1.1^n)\) or argue that none exists.

  • [(folklore)] What is the algorithmic complexity of the minimum spanning tree problem?  See also here.

  • [(folklore)] Can integer factorization be done in polynomial time?  See also here.

  • [Gonzalez:] In the Euclidean \(k\)-center problem, given a set of \(n\) points in the Euclidean space and a positive integer \(k\), the problem is to cover the set by \(k\) congruent balls centered at the points so that the diameter of the balls is minimized. A factor \(2\) approximation algorithm is available.  See also here.
    Provide a ratio \(1.99\) approximation for \(k\)-center in the plane or argue that none exists.

  • [Christofides:] Christofides' algorithm for the metric traveling salesman problem is a \(3/2\)-approximation algorithm. Provide a \(1.49\)-approximation algorithm or argue that none exists.  See also here (Ch. 17).

  • [Dumitrescu, Tóth:] Is there a constant-factor approximation algorithm for TSP with convex bodies in the plane? (or for MST with convex bodies in the plane)?  See also here (p. 375).

  • [Dumitrescu, Tóth:] Is TSP with disks in the plane APX-hard? Is TSP with convex bodies in the plane APX-hard?  See also here (p. 375).

  • [Fekete:] Is the MAX TSP NP-hard in the Euclidean plane? What if the tour is required to be noncrossing?  See also here (Ch. 31).

  • [Alon, Rajagopalan, Suri:] Let \(S\) be a set of \(n\) points in the plane (say, with no three points collinear). What is the computational complexity of the following problems?
    (i) Compute a longest non-crossing spanning tree.
    (ii) Compute a longest non-crossing perfect matching (\(n\): even).
    (iii) Compute a longest non-crossing hamiltonian path (or cycle).
     See also here.

  • (folklore) Does every finite set of points in the plane admit a plane geometric graph whose vertex set is the given set of points that has maximum degree three and whose Euclidean stretch factor is bounded from above by a constant?  See also here (Problem 15).

  • [Williamson and Shmoys:] Devise a polynomial-time algorithm that uses \(O(\log^c{n})\) colors for a \(3\)-colorable graph, or argue that none exists.  See also here (Ch. 17).

  • [Vazirani:] Provide a factor \(0.51\) approximation algorithm for the following problem or argue that none exists. Given a directed graph \(G=(V,E)\), pick a subset of edges from \(E\) of maximum size so that the resulting subgraph is acyclic.  See also here (p. 7).

  • (folklore) Give a polynomial-time algorithm for computing a constant-factor approximation of the minimum number of point guards needed to cover a simple polygon or argue that none exists.  See also here (Ch. 30).

  • Knuth: Prove or disprove that the number of isomorphism classes of simple pseudoline arrangements is \(2^{{n \choose 2} + o(n^2)}\).  See also here (Ch. 5).

  • (folklore) What is the maximum complexity of the \(k\)-level in an arrangement of \(n\) lines in the plane?  See also here (Ch. 28).

  • [Kára, Pór, Wood:] Does there exist for every \(k\) a number \(n = n(k)\) such that in any set \(P\) of \(n\) points in the plane there are \(k\) elements that are either collinear or pairwise see each other? (Two elements of \(P\) see each other if the segment connecting them does not pass through any other point of \(P\).)  See also here.

  • [Erdős, Szekeres:] Do every \( 2^{n-2} + 1 \) points in the plane (no 3 collinear) determine a convex \( n \)-gon?  See also here.

  • [Larman, Matoušek, Pach, Töröcsik:] What is the largest positive number \(f=f(n)\) such that any family of \(n\) convex bodies in the plane has a subfamily of \(f\) members that are either pairwise disjoint or pairwise intersecting? It is known that \(n^{0.2} \leq f(n) \leq n^{0.4207}\).  See also here (Ch. 10).

  • (folklore) Does every familiy of \(n\) axis-parallel rectangles in the plane contain a subfamily of \(\Omega(\sqrt{n})\) members that are either pairwise disjoint or pairwise intersecting? It is known that one can find a subfamily of size \(\Omega(\sqrt{n/\log{n}})\).  See also here (Ch. 9).


Other collections of open problems:

As with this page, these collections may not be up-to-date.

David Aldous's list of open problems

List of open questions by Antoine Amarilli

Boris Bukh's list of interesting problems

Peter Cameron's collection of "old problems"

Vašek Chvátal's list of unsolved problems

Joshua Cooper's list of open problems in combinatorics

Jeff Erickson's list of open algorithmic problems

Douglas B. West's list of open problems - graph theory and combinatorics

The Open Problems Project (Erik D. Demaine - Joseph S. B. Mitchell - Joseph O'Rourke)

Open Problem Garden (created by Matt DeVos and Robert Šámal)

  • Problems from British Combinatorial Conferences edited by Peter Cameron