AlgOrEsEArch

AlgOrEsEArch

provides expertise and consulting service in algorithm design and analysis

provides collaboration on research projects in the area of algorithms

provides tailored solutions for specific algorithmic problems

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

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

Papers

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.
Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth, On the stretch factor of polygonal chains, SIAM Journal on Discrete Mathematics, 35(3), 2021, 1592-1614. Preprint available on arXiv.
Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth, Sparse hop spanners for unit disk graphs, Computational Geometry: Theory and Applications, 100: 101808, (2022). A preliminary version in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), December 14-18, 2020, Hong Kong, China (Virtual Conference), Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl, vol. 181, pp. 57:1-57:17. Preprint available on arXiv.
Adrian Dumitrescu, Finding triangles or independent sets, manuscript, 2021. Preprint available on arXiv.
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.
Adrian Dumitrescu and Josef Tkadlec, Lattice and non-lattice piercing of axis-parallel rectangles: exact algorithms and a separation result, manuscript, 2022. Preprint available on arXiv.
Adrian Dumitrescu, The Dirac-Goodman-Pollack conjecture, Discrete & Computational Geometry, to appear. Preprint available on arXiv.
Adrian Dumitrescu and Csaba D. Tóth, Finding points in convex position in density-restricted sets, manuscript, 2022. Preprint available on arXiv.
Adrian Dumitrescu, Peeling sequences, Mathematics, 10(22), 2022. Preprint available on arXiv.
Adrian Dumitrescu, Two-sided convexity testing with certificates, manuscript, 2022. 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."

[Knuth:] Let \(S(n)\) be the minimum number of comparisons that will suffice to sort \(n\) elements. Determine the exact value of \(S(n)\) for infinitely many \(n\). See also here (Vol. 3, Ch. 5) .

[Aigner (for (i):] Let \(V_i(n)\) be the minimum number of comparisons needed in the worst case to select the \(i\)-th smallest element from \(n\) elements.
(i) Let \(i < n/2\). Prove or disprove that \(V_i(n) \leq V_{i+1}(n)\). See also here.
(ii) Prove or disprove that \(V_7(16) =30\).
(iii) Prove or disprove that \(V_6(17) =31\).
(iv) Prove or disprove that \(V_4(19) =29\).

[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.

(folklore) The 3SUM problem asks if a given set of \(n\) real numbers contains three elements that sum to zero. Can this problem be solved in strongly sub-quadratic time, that is, in time \(O(n^{2-\varepsilon})\) for some constant \(\varepsilon>0\) ? How about INTEGER 3SUM, where each entry is an integer whose absolute value is, say, at most \(n^3\)? See also here.

(folklore) Prove or disprove: Given \(n\) points in the plane, no three of which are collinear, it can be determined in \(O(n)\) time if they are in convex position. It is conjectured that the answer is negative. 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) and here.

[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).

[Bereg, Dumitrescu, Jiang:] Consider a finite set of axis-parallel squares. How small can the largest area covered by a disjoint subset of squares be relative to the area of the union? See also here.

[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).

[Pach, Tardos:] Let \(S\) be a set of \(n\) disjoint axis-aligned rectangles in the plane. Prove or disprove that there exists a BSP that separates \(c n\) members of \(S\) (without being fragmented by the cuts), for some positive constant \(c>0\). See also here.

[Dumitrescu, Jiang:] Given an axis-parallel rectangle \(U\) in the plane containing \(n\) points, the problem of computing a maximum-area axis-parallel empty rectangle contained in \(U\) is one of the oldest in computational geometry. Prove or disprove that the number of maximum-area empty rectangles amidst \(n\) points in the plane is \(O(n)\). See also here.

AlgOrEsEArch

Books

Papers

Open Problems

Other collections of open problems: