File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Reconstructing numbers from pairwise function values

TitleReconstructing numbers from pairwise function values
Authors
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 142-152 How to Cite?
AbstractThe turnpike problem is one of the few "natural" problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set A={a 1,a 2,⋯,a n } from pairwise function values {f(a i ,a j ) | 1≤i, j≤n} for a given bivariate function f. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when f is monotone and non-trivial bounds on the number of solutions when f is the sum. We also generalize previous backtracking and algebraic algorithms for the turnpike problem such that they work for the family of anti-monotone functions and linear-decomposable functions. Finally, we propose an efficient algorithm for the string reconstruction problem, which is related to an approach to protein reconstruction. © 2009 Springer-Verlag Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/188486
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChen, Sen_US
dc.contributor.authorHuang, Zen_US
dc.contributor.authorKannan, Sen_US
dc.date.accessioned2013-09-03T04:08:41Z-
dc.date.available2013-09-03T04:08:41Z-
dc.date.issued2009en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 142-152en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/188486-
dc.description.abstractThe turnpike problem is one of the few "natural" problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set A={a 1,a 2,⋯,a n } from pairwise function values {f(a i ,a j ) | 1≤i, j≤n} for a given bivariate function f. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when f is monotone and non-trivial bounds on the number of solutions when f is the sum. We also generalize previous backtracking and algebraic algorithms for the turnpike problem such that they work for the family of anti-monotone functions and linear-decomposable functions. Finally, we propose an efficient algorithm for the string reconstruction problem, which is related to an approach to protein reconstruction. © 2009 Springer-Verlag Berlin Heidelberg.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.titleReconstructing numbers from pairwise function valuesen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@cis.upenn.eduen_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-10631-6_16en_US
dc.identifier.scopuseid_2-s2.0-75649088149en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-75649088149&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume5878 LNCSen_US
dc.identifier.spage142en_US
dc.identifier.epage152en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridChen, S=35361606300en_US
dc.identifier.scopusauthoridHuang, Z=55494568500en_US
dc.identifier.scopusauthoridKannan, S=7102340548en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats