This is a list of my papers with known issues, including some
discussion of the issues;
- Bala Kalyanasundaram, Kirk Pruhs: Constructing Competitive
Tours from Local Information. Theor. Comput. Sci. 130(1):
125-138 (1994). ICALP 1993: 102-113
- Explanation of the issues: We add a jump edge (x, y) when
certain conditions are met that insure that we can afford to
travel to vertex y from vertex x. These conditions may however
later not hold. So later it may be too expensive to travel
from x to y. A counter example to the correctness of the
algorithm, as well as a fix are given in: Nicole Megow, Kurt
Mehlhorn, Pascal Schweitzer: Online graph exploration: New
results on old and new algorithms. Theor. Comput. Sci. 463:
62-72 (2012).
ICALP (2) 2011: 478-489.
- Negative spin: Our algorithm was wrong.
- Positive spin: All the necessary ideas are there in the
original paper, and they just needed to be applied with more
care.
- Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs,
Kevin Schewior, Michele Scquizzato: Chasing Convex Bodies and
Functions. LATIN 2016: 68-81
- Explanation of the issues: The proof of Lemma 2, which
reduces online convex optimization to online lazy convex body
chasing, implicitly assumes radial symmetry for the convex
function. It isn't too hard to come up with functions that do
not have radial symmetry and that can not be decomposed into
lazy convex bodies as in the proof.
- Negative spin: Convex functions with radial symmetry are
very special, and this significantly weakens the evidence that
online convex optimization isn't harder than online convex
body chasing.
- Positive spin: There is no reason to think that radial
symmetry makes online convex optimization any easier, and thus
this does not significantly weak the evidence that online
convex optimization isn't harder than online convex body
chasing. And in fact the claimed reduction is possible, but it
requires more sophisticated methods. See Chasing Convex
Bodies with Linear Competitive Ratio C.J. Argue, Anupam
Gupta, Guru Guruganesh, Ziye Tang and trace the references
backwards if its not there.
- Jeff Edmonds, Kirk Pruhs: Balanced Allocations of Cake. FOCS
2006: 623-634. Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki:
Confidently Cutting a Cake into Approximately Fair Pieces. AAIM
2008: 155-164
- Explanation of issues: In trying to combine these papers
into one journal paper, I came to the conclusion that some of
the arguments need to be handled a bit more carefully. I
thought all the tools/insights to do this were there, but it
was a pain. So when I ended up getting busy, and this got set
aside. And now its been enough time that I can't remember
specifics of the issues.