Relevant bibliographies by topics / Shortest common superstring problem

Academic literature on the topic 'Shortest common superstring problem'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Shortest common superstring problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Shortest common superstring problem"

1

Gorbenko, Anna, and Vladimir Popov. "The shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 2353–56. http://dx.doi.org/10.12988/ams.2013.13212.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gorbenko, A., and V. Popov. "On multiple occurrences shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 641–44. http://dx.doi.org/10.12988/ams.2013.13056.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bilò, Davide, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, and Anna Zych. "Reoptimization of the Shortest Common Superstring Problem." Algorithmica 61, no. 2 (June 15, 2010): 227–51. http://dx.doi.org/10.1007/s00453-010-9419-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Popov, V. "On reoptimization of the shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 1195–97. http://dx.doi.org/10.12988/ams.2013.13109.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Laube, Uli, and Maik Weinard. "CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM." International Journal of Foundations of Computer Science 16, no. 06 (December 2005): 1219–30. http://dx.doi.org/10.1142/s0129054105003777.

Full text
Abstract:
We investigate the shortest common superstring problem (SCSSP). As SCSSP is APX-complete it cannot be approximated within an arbitrarily small performance ratio. One heuristic that is widely used is the notorious greedy heuristic. It is known, that the performance ratio of this heuristic is at least 2 and not worse than 4. It is conjectured that the greedy heuristic's performance ratio is in fact 2 (the greedy conjecture). Even the best algorithms introduced for SCSSP can only guarantee an upper bound of 2.5. In [11] an even stronger version of the greedy conjecture is proven for a restricted class of orders in which strings are merged. We extend these results by broadening the class for which this stronger version can be established. We also show that the Triple inequality, introduced in [11] and crucial for their results, is inherently insufficient to carry the proof for the greedy conjecture in the general case. Finally we describe how linear programming can be used to support research along this line.
APA, Harvard, Vancouver, ISO, and other styles
6

Ma, Bin. "Why greed works for shortest common superstring problem." Theoretical Computer Science 410, no. 51 (November 2009): 5374–81. http://dx.doi.org/10.1016/j.tcs.2009.09.014.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Zaritsky, Assaf, and Moshe Sipper. "Coevolving solutions to the shortest common superstring problem." Biosystems 76, no. 1-3 (August 2004): 209–16. http://dx.doi.org/10.1016/j.biosystems.2004.05.013.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Turner, Jonathan S. "Approximation algorithms for the shortest common superstring problem." Information and Computation 83, no. 1 (October 1989): 1–20. http://dx.doi.org/10.1016/0890-5401(89)90044-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Laube, U., and M. Weinard. "ERRATUM: "CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM"." International Journal of Foundations of Computer Science 17, no. 01 (February 2006): 247. http://dx.doi.org/10.1142/s0129054106003796.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

GLOOR, GREG, LILA KARI, MICHELLE GAASENBEEK, and SHENG YU. "TOWARDS A DNA SOLUTION TO THE SHORTEST COMMON SUPERSTRING PROBLEM." International Journal on Artificial Intelligence Tools 08, no. 04 (December 1999): 385–99. http://dx.doi.org/10.1142/s0218213099000269.

Full text
Abstract:
This paper proposes a DNA algorithm for solving an NP-complete problem (The Shortest Common Superstring Problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Shortest common superstring problem"

1

Plociennik, Kai. "From Worst-Case to Average-Case Efficiency – Approximating Combinatorial Optimization Problems." Doctoral thesis, Universitätsbibliothek Chemnitz, 2011. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-65314.

Full text
Abstract:
In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.
APA, Harvard, Vancouver, ISO, and other styles
2

Plociennik, Kai. "From Worst-Case to Average-Case Efficiency – Approximating Combinatorial Optimization Problems: From Worst-Case to Average-Case Efficiency – Approximating Combinatorial Optimization Problems." Doctoral thesis, 2010. https://monarch.qucosa.de/id/qucosa%3A19469.

Full text
Abstract:
In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.
APA, Harvard, Vancouver, ISO, and other styles
3

Lee, Pei-Chen, and 李佩真. "Application of Stochastic Optimization Methodology to Bioinformatics -- A Case Study on Applying Ant Colony Optimization to the Shortest Superstring problem." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/8cc5d6.

Full text
Abstract:
碩士
國立臺北科技大學
工業工程與管理研究所
95
Bioinformatics has received wide attention in recent years. It is interesting to see how stochastic optimization methodologies such as genetic algorithm, simulated annealing and ant colony optimization, that can be applied to solve problems in bioinformatics. Among many research problems in bioinformatics, the shortest superstring problem has wide applications in many research areas, such as DNA sequencing and data compression. However, the problem is NP-hard and difficult to solve efficiently. In the literature, the ant colony optimization algorithm has been reported to be successfully applied to many combinatorial problems, such as the traveling salesperson problem and the assignment problem. In this paper, we describe the use of the ant colony optimization algorithm to solve the shortest superstring problem, which highlights a way for applying stochastic optimization methodologies to solve problem in bioinformatics.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Shortest common superstring problem"

1

Bilò, Davide, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, and Anna Zych. "Reoptimization of the Shortest Common Superstring Problem." In Combinatorial Pattern Matching, 78–91. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02441-2_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

López-Rodríguez, D., and E. Mérida-Casermeiro. "Shortest Common Superstring Problem with Discrete Neural Networks." In Adaptive and Natural Computing Algorithms, 62–71. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-04921-7_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

González, Luis C., Heidi J. Romero, and Carlos A. Brizuela. "A Genetic Algorithm for the Shortest Common Superstring Problem." In Genetic and Evolutionary Computation – GECCO 2004, 1305–6. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24855-2_139.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

González-Gurrola, Luis C., Carlos A. Brizuela, and Everardo Gutiérrez. "A Genetic Algorithm for the Shortest Common Superstring Problem." In Advances in Artificial Intelligence – IBERAMIA 2004, 851–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-30498-2_85.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Crochemore, Maxime, Marek Cygan, Costas Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. "Algorithms for Three Versions of the Shortest Common Superstring Problem." In Combinatorial Pattern Matching, 299–309. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13509-5_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Nikolaev, Maksim S. "All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent." In String Processing and Information Retrieval, 61–67. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-86692-1_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bongartz, Dirk. "On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem." In SOFSEM 2000: Theory and Practice of Informatics, 298–306. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44411-4_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Gevezes, Theodoros P., and Leonidas S. Pitsoulis. "The Shortest Superstring Problem." In Optimization in Science and Engineering, 189–227. New York, NY: Springer New York, 2014. http://dx.doi.org/10.1007/978-1-4939-0808-0_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Plociennik, Kai. "A Probabilistic PTAS for Shortest Common Superstring." In Mathematical Foundations of Computer Science 2009, 624–35. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03816-7_53.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Gotthilf, Zvi, Moshe Lewenstein, and Alexandru Popa. "On Shortest Common Superstring and Swap Permutations." In String Processing and Information Retrieval, 270–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-16321-0_28.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Shortest common superstring problem"

1

Leonova, Yuliya F., and Anatoly V. Panyukov. "Application of the Cycles Merging Algorithm to the Shortest Common Superstring Problem." In 2020 Global Smart Industry Conference (GloSIC). IEEE, 2020. http://dx.doi.org/10.1109/glosic50886.2020.9267863.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Buzdalov, Maxim, and Fedor Tsarev. "An Evolutionary Approach to Hard Test Case Generation for Shortest Common Superstring Problem." In 2013 BRICS Congress on Computational Intelligence & 11th Brazilian Congress on Computational Intelligence (BRICS-CCI & CBIC). IEEE, 2013. http://dx.doi.org/10.1109/brics-cci-cbic.2013.24.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Khadiev, Kamil, and Carlos M. Bosch Machado. "Quantum algorithm for the shortest superstring problem." In International Conference on Micro- and Nano-Electronics 2021, edited by Konstantin V. Rudenko and Vladimir F. Lukichev. SPIE, 2022. http://dx.doi.org/10.1117/12.2624618.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Khalid, Ali, Anthony Enem, and Eduardo Colmenares. "Distributed Cache-Reduction Approach to DNA Sequencing Using a Greedy Algorithm for the Shortest Common Superstring." In 2018 International Conference on Computational Science and Computational Intelligence (CSCI). IEEE, 2018. http://dx.doi.org/10.1109/csci46756.2018.00267.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Saifullah, C. M. Khaled, and Md Rafiqul Islam. "Solving shortest common supersequence problem using chemical reaction optimization." In 2016 5th International Conference on Informatics, Electronics and Vision (ICIEV). IEEE, 2016. http://dx.doi.org/10.1109/iciev.2016.7760187.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Barone, Paolo, Paola Bonizzoni, Gianluca Delta Vedova, and Giancarlo Mauri. "An approximation algorithm for the shortest common supersequence problem." In the 2001 ACM symposium. New York, New York, USA: ACM Press, 2001. http://dx.doi.org/10.1145/372202.372275.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Kubalik, Jiri. "Evolutionary-based iterative local search algorithm for the shortest common supersequence problem." In the 13th annual conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/2001576.2001620.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ning, Kang, and Hon Wai Leong. "Towards a Better Solution to the Shortest Common Supersequence Problem: A Post." In 2006 International Multi-Symposiums on Computer and Computational Sciences (IMSCCS). IEEE, 2006. http://dx.doi.org/10.1109/imsccs.2006.136.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kubalík, Jiří. "Efficient stochastic local search algorithm for solving the shortest common supersequence problem." In the 12th annual conference. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1830483.1830529.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Romano, Giulia, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. "The Power of Media Agencies in Ad Auctions: Improving Utility through Coordinated Bidding." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/66.

Full text
Abstract:
The increasing competition in digital advertising induced a proliferation of media agencies playing the role of intermediaries between advertisers and platforms selling ad slots. When a group of competing advertisers is managed by a common agency, many forms of collusion, such as bid rigging, can be implemented by coordinating bidding strategies, dramatically increasing advertisers' value. We study the problem of finding bids and monetary transfers maximizing the utility of a group of colluders, under GSP and VCG mechanisms. First, we introduce an abstract bid optimization problem---called weighted utility problem (WUP)---, which is useful in proving our results. We show that the utilities of bidding strategies are related to the length of paths in a directed acyclic weighted graph, whose structure and weights depend on the mechanism under study. This allows us to solve WUP in polynomial time by finding a shortest path of the graph. Next, we switch to our original problem, focusing on two settings that differ for the incentives they allow for. Incentive constraints ensure that colluders do not leave the agency, and they can be enforced by implementing monetary transfers between the agency and the advertisers. In particular, we study the arbitrary transfers setting, where any kind of monetary transfer to and from the advertisers is allowed, and the more realistic limited liability setting, in which no advertiser can be paid by the agency. In the former, we cast the problem as a WUP instance and solve it by our graph-based algorithm, while, in the latter, we formulate it as a linear program with exponentially-many variables efficiently solvable by applying the ellipsoid algorithm to its dual. This requires to solve a suitable separation problem in polynomial time, which can be done by reducing it to the weighted utility problem a WUP instance.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Shortest common superstring problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography