|
Give me the details give me the number Research it further research it further [VM] |
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
|
|
Give me the details give me the number Research it further research it further [VM] |
[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.
[Karp:]
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 and the paper by Howgrave-Graham and Joux (2010).
(a) Construct an \(O(1.1^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.
Is there an exact algorithm for CLIQUE with time complexity \(O(1.1^n)\)?
(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, 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 and 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.
[Danzer:]
Given a set of \(n\) points in the unit square, what is the area of the largest
empty convex region contained in the square?
[García, Noy, and Tejel:] Prove (or disprove) that there exist \(n\) points in the plane in general position that admit \(\Omega(3.1^n)\) noncrossing perfect matchings.
[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.4054}\).
See also
here (Ch. 10).
(folklore)
For a family \(F\) of axis-parallel rectangles in \(\mathbb{R}^2\),
let \(\tau=\tau(F)\) denote its piercing number and \(\nu=\nu(F)\) denote its independence number.
Prove or disprove that \(\tau = O(\nu)\). It is known that \(\tau =O(\nu (\log \log {\nu})^2)\).
Note that Wegner's conjecture \(\tau \leq 2 \nu -1\), from 1965,
has been recently disproved.
See also
here and
here.
(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 \log{n})\).
See also here (Ch. 9). and
here.
[Pach, Tardos:]
Let \(S\) be a set of \(n\) disjoint axis-aligned rectangles in the plane.
Prove or disprove that there exists a binary space partition (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.
[Itai, Rodeh:]
Let \(G\) be a graph with \(n\) vertices.
Can triangle detection be done in quadratic or nearly quadratic time?
The current record is about \(O(n^{2.38})\), achieved via matrix multiplication.
Is there a combinatorial algorithm for triangle detection that runs in truly subcubic time?
See also here.
[Woeginger:] Let \(G\) be a graph with \(n\) vertices. Can \(K_{10}\) detection be done in \(O(n^{7.5})\) time? [see his 2008 survey on exact algorithms]
[Woeginger:] Is there an exact algorithm for TSP with time complexity \(O(1.99^n)\)? [see his 2008 survey on exact algorithms]
[Knauer, Spillner:]
Let \(S\) be a set of \(n\geq 3\) points in \(\mathbb{R}^2\).
A convex polygon is empty if its interior is disjoint from \(S\).
A convex partition of \(S\) is a partition of the convex hull \({\rm conv}(S)\)
into empty convex polygons (called tiles) such that the vertices of the tiles are in \(S\).
Is there a polynomial-time algorithm for computing a minimum convex partition of a given set of \(n\) points
in the plane? Can the ratio \(30/11\) approximation be improved?
See also here.
[Dumitrescu, Pach:] What is the minimum number of monochromatic parts whose convex hulls are pairwise disjoint, into which a 2-colored set of \(n\) points in \(\mathbb{R}^3\) (no \(4\) coplanar) can be partitioned? Is it \(o(n)\)? Can an optimal partition be efficiently computed (in the plane or in \(3\)-space)? See also here.
[Bose, Hurtado, Rivera-Campo, Wood:]
Does there exists a positive constant \(c<1\), such that every complete geometric graph on \(n\) points
in general position in the plane can be partitioned into at most \(cn\) noncrossing subgraphs?
Devise a polynomial-time algorithm for this task.
See also here.
Two special cases are addressed here.
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
List of unsolved problems in computer science From Wikipedia
List of unsolved problems in mathematics From Wikipedia