Paper retraction: On the hardness of embeddings between two finite metrics

Matthew Cary; Atri Rudra; Ashish Sabharwal

doi:10.1007/978-3-540-73420-8_81

Paper retraction: On the hardness of embeddings between two finite metrics

Matthew Cary
, Atri Rudra
, Ashish Sabharwal

Department of Computer Science and Engineering

University of Washington

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We regret to report that we have found an error in our paper "On the Hardness of Embeddings Between Two Finite Metrics," which appeared in the Proceedings of the 32^nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005. In that paper, we sought to prove NP-hardness of approximating the minimum distortion when one finite metric is embedded into another. While the fairly involved reduction we presented was correct, the Directed Disjoint Cycle Cover (DDCC) problem we were reducing from has a polynomial-time algorithm, as noticed later by Jiri Sgall. Despite much effort, we have not been able to find an alternate reduction, and it remains open whether our claimed hardness of approximation results still hold.

Original language	English
Title of host publication	Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings
Publisher	Springer Verlag
Pages	949
Number of pages	1
ISBN (Print)	3540734198, 9783540734192
DOIs	https://doi.org/10.1007/978-3-540-73420-8_81
State	Published - 2007
Event	34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland Duration: Jul 9 2007 → Jul 13 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4596 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	34th International Colloquium on Automata, Languages and Programming, ICALP 2007
Country/Territory	Poland
City	Wroclaw
Period	07/9/07 → 07/13/07

Access to Document

10.1007/978-3-540-73420-8_81

Cite this

Cary, M., Rudra, A., & Sabharwal, A. (2007). Paper retraction: On the hardness of embeddings between two finite metrics. In Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings (pp. 949). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4596 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73420-8_81

Cary, Matthew ; Rudra, Atri ; Sabharwal, Ashish. / Paper retraction : On the hardness of embeddings between two finite metrics. Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, 2007. pp. 949 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a2f45a7e51864b65b3eddcdc68a1ac90,

title = "Paper retraction: On the hardness of embeddings between two finite metrics",

abstract = "We regret to report that we have found an error in our paper {"}On the Hardness of Embeddings Between Two Finite Metrics,{"} which appeared in the Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005. In that paper, we sought to prove NP-hardness of approximating the minimum distortion when one finite metric is embedded into another. While the fairly involved reduction we presented was correct, the Directed Disjoint Cycle Cover (DDCC) problem we were reducing from has a polynomial-time algorithm, as noticed later by Jiri Sgall. Despite much effort, we have not been able to find an alternate reduction, and it remains open whether our claimed hardness of approximation results still hold.",

author = "Matthew Cary and Atri Rudra and Ashish Sabharwal",

year = "2007",

doi = "10.1007/978-3-540-73420-8\_81",

language = "English",

isbn = "3540734198",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "949",

booktitle = "Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings",

address = "Germany",

note = "34th International Colloquium on Automata, Languages and Programming, ICALP 2007 ; Conference date: 09-07-2007 Through 13-07-2007",

}

Cary, M, Rudra, A & Sabharwal, A 2007, Paper retraction: On the hardness of embeddings between two finite metrics. in Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4596 LNCS, Springer Verlag, pp. 949, 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, Wroclaw, Poland, 07/9/07. https://doi.org/10.1007/978-3-540-73420-8_81

Paper retraction: On the hardness of embeddings between two finite metrics. / Cary, Matthew; Rudra, Atri; Sabharwal, Ashish.
Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, 2007. p. 949 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4596 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Paper retraction

T2 - 34th International Colloquium on Automata, Languages and Programming, ICALP 2007

AU - Cary, Matthew

AU - Rudra, Atri

AU - Sabharwal, Ashish

PY - 2007

Y1 - 2007

N2 - We regret to report that we have found an error in our paper "On the Hardness of Embeddings Between Two Finite Metrics," which appeared in the Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005. In that paper, we sought to prove NP-hardness of approximating the minimum distortion when one finite metric is embedded into another. While the fairly involved reduction we presented was correct, the Directed Disjoint Cycle Cover (DDCC) problem we were reducing from has a polynomial-time algorithm, as noticed later by Jiri Sgall. Despite much effort, we have not been able to find an alternate reduction, and it remains open whether our claimed hardness of approximation results still hold.

AB - We regret to report that we have found an error in our paper "On the Hardness of Embeddings Between Two Finite Metrics," which appeared in the Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005. In that paper, we sought to prove NP-hardness of approximating the minimum distortion when one finite metric is embedded into another. While the fairly involved reduction we presented was correct, the Directed Disjoint Cycle Cover (DDCC) problem we were reducing from has a polynomial-time algorithm, as noticed later by Jiri Sgall. Despite much effort, we have not been able to find an alternate reduction, and it remains open whether our claimed hardness of approximation results still hold.

UR - https://www.scopus.com/pages/publications/38149127134

U2 - 10.1007/978-3-540-73420-8_81

DO - 10.1007/978-3-540-73420-8_81

M3 - Conference contribution

AN - SCOPUS:38149127134

SN - 3540734198

SN - 9783540734192

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 949

BT - Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings

PB - Springer Verlag

Y2 - 9 July 2007 through 13 July 2007

ER -

Cary M, Rudra A, Sabharwal A. Paper retraction: On the hardness of embeddings between two finite metrics. In Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag. 2007. p. 949. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73420-8_81

Paper retraction: On the hardness of embeddings between two finite metrics

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this