Academic literature on the topic 'NP-Hard optimization problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'NP-Hard optimization problems.'
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 "NP-Hard optimization problems"
Cai, Liming, David Juedes, and Iyad Kanj. "The inapproximability of non-NP-hard optimization problems." Theoretical Computer Science 289, no. 1 (October 2002): 553–71. http://dx.doi.org/10.1016/s0304-3975(01)00343-7.
Full textKremer, Ulrich. "Optimal and Near–Optimal Solutions for Hard Compilation Problems." Parallel Processing Letters 07, no. 04 (December 1997): 371–78. http://dx.doi.org/10.1142/s0129626497000371.
Full textHidalgo-Herrero, Mercedes, Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio. "Comparing Problem Solving Strategies for NP-hard Optimization Problems." Fundamenta Informaticae 124, no. 1-2 (2013): 1–25. http://dx.doi.org/10.3233/fi-2013-822.
Full textŽerovnik, Janez. "Heuristics for NP-hard optimization problems - simpler is better!?" Logistics & Sustainable Transport 6, no. 1 (November 1, 2015): 1–10. http://dx.doi.org/10.1515/jlst-2015-0006.
Full textArora, Sanjeev. "Approximation schemes for NP-hard geometric optimization problems: a survey." Mathematical Programming 97, no. 1 (July 2003): 43–69. http://dx.doi.org/10.1007/s10107-003-0438-y.
Full textToktoshov, Gulzhigit Y., Anastasiya N. Yurgenson, and Denis A. Migov. "COMPLEXITY ANALYSIS OF OPTIMIZATION PROBLEMS OF UTILITYCOMMUNICATIONS NETWORKS." T-Comm 14, no. 9 (2020): 17–23. http://dx.doi.org/10.36724/2072-8735-2020-14-9-17-23.
Full textHorng, Shih-Cheng, and Shieh-Shing Lin. "Coupling Elephant Herding with Ordinal Optimization for Solving the Stochastic Inequality Constrained Optimization Problems." Applied Sciences 10, no. 6 (March 19, 2020): 2075. http://dx.doi.org/10.3390/app10062075.
Full textHorng, Shih-Cheng, and Shieh-Shing Lin. "Embedding Ordinal Optimization into Tree–Seed Algorithm for Solving the Probabilistic Constrained Simulation Optimization Problems." Applied Sciences 8, no. 11 (November 3, 2018): 2153. http://dx.doi.org/10.3390/app8112153.
Full textYu, Fa Hong, Wei Zhi Liao, and Mei Jia Chen. "An Novel Estimation of Distribution Algorithm for TSP." Applied Mechanics and Materials 373-375 (August 2013): 1089–92. http://dx.doi.org/10.4028/www.scientific.net/amm.373-375.1089.
Full textToth, Paolo. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems." European Journal of Operational Research 125, no. 2 (September 2000): 222–38. http://dx.doi.org/10.1016/s0377-2217(99)00453-1.
Full textDissertations / Theses on the topic "NP-Hard optimization problems"
Ono, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.
Find full textLi, Nan. "Algorithms for NP-hard Optimization Problems and Cluster Analysis." Diss., Temple University Libraries, 2017. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/482725.
Full textPh.D.
The set cover problem, weighted set cover problem, minimum dominating set problem and minimum weighted dominating set problem are all classical NP-hard optimization problems of great importance in both theory and real applications. Since the exact algorithms, which require exhaustive exploration of exponentially many options, are infeasible in practice, approximation algorithms and heuristic algorithms are widely used to find reasonably good solutions in polynomial time. I propose novel algorithms for these problems. My algorithms for the weighted set cover and minimum weighted dominating set problems are based on a three-step strategy. For the weighted set cover problem, in the first step, we reserve the sets indispensable for the optimal solution and reduce the problem size. In the second step, we build a robust solution with a novel greedy heuristic. Sets are iteratively selected according to a measure which integrates the weight, the coverage gain for the current iteration and the global coverage capacity of each set. It favors the sets that have smaller weights and better extend or consolidate the coverage, especially on the items that are contained in less sets. Since the obtained solution tends to have a robust coverage, in the third step, we further improve it by removing the redundant sets in an efficient way. For the minimum weighted dominating set problem, we first reserve the indispensable vertices for the optimal solution. Then we convert it into a weighted set cover problem to solve it. These two algorithms can be used to solve the set cover problem and minimum dominating set problem by simply considering all the sets or vertices as having the same weights. Extensive experimental evaluations on a large number of synthetic and real-world set cover instances and graphs from many domains demonstrate the superiority of my algorithms over state-of-the-art. Cluster analysis is a fundamental problem in data analysis, and has extensive applications in artificial intelligence, statistics and even in social sciences. The goal is to partition the data objects into a set of groups (clusters) such that objects in the same group are similar, while objects in different groups are dissimilar. Most of the existing algorithms for clustering are designed to handle data with only one type of attributes, e.g. continuous, categorical or ordinal. Mixed data clustering has received relatively less attention, despite the fact that data with mixed types of attributes are common in real applications. I propose a novel affinity learning based framework for mixed data clustering, which includes: how to process data with mixed-type attributes, how to learn affinities between data points, and how to exploit the learned affinities for clustering. In the proposed framework, each original data attribute is represented with several abstract objects defined according to the specific data type and values. Each attribute value is transformed into the initial affinities between the data point and the abstract objects of attribute. I refine these affinities and infer the unknown affinities between data points by taking into account the interconnections among the attribute values of all data points. The inferred affinities between data points can be exploited for clustering. Alternatively, the refined affinities between data points and the abstract objects of attributes can be transformed into new data features for clustering. Experimental results on many real world data sets demonstrate that the proposed framework is effective for mixed data clustering. This work was published in our IJCAI 2017 paper Li & Latecki (2017). Clustering aggregation, also known as consensus clustering or clustering ensemble, aims to find a single superior clustering from a number of input clusterings obtained by different algorithms with different parameters. I formulate clustering aggregation as a special instance of the maximum-weight independent set (MWIS) problem. For a given data set, an attributed graph is constructed from the union of the input clusterings. The vertices, which represent the distinct clusters, are weighted by an internal index measuring both cohesion and separation. The edges connect the vertices whose corresponding clusters overlap. Intuitively, an optimal aggregated clustering can be obtained by selecting an optimal subset of non-overlapping clusters partitioning the data set together. I formalize this intuition as the MWIS problem on the attributed graph, i.e., finding the heaviest subset of mutually non-adjacent vertices. This MWIS problem exhibits a special structure. Since the clusters of each input clustering form a partition of the dataset, the vertices corresponding to each clustering form a maximal independent set (MIS) in the attributed graph. I propose a variant of simulated annealing method that takes advantage of this special structure. My algorithm starts from each MIS, which is close to a distinct local optimum of the MWIS problem, and utilizes a local search heuristic to explore its neighborhood in order to find the MWIS. Extensive experiments on many challenging data sets show that both my algorithm for the maximum-weight independent set problem and my approach to the application of clustering aggregation achieve good performance. This work was published in our NIPS 2012 paper Li & Latecki (2012). Some new results were published in our IJCAI 2017 paper Fan et al. (2017).
Temple University--Theses
Canzar, Stefan. "Lagrangian Relaxation - Solving NP-hard Problems in Computational Biology via Combinatorial Optimization." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00388521.
Full textAwasthi, Abhishek [Verfasser], Oliver [Akademischer Betreuer] Kramer, and Jörg [Akademischer Betreuer] Lässig. "Optimization of NP-hard Scheduling Problems by Developing Timing Algorithms and Parallelization / Abhishek Awasthi ; Oliver Kramer, Jörg Lässig." Oldenburg : BIS der Universität Oldenburg, 2016. http://d-nb.info/1123210772/34.
Full textAwasthi, Abhishek Verfasser], Oliver [Akademischer Betreuer] [Kramer, and Jörg [Akademischer Betreuer] Lässig. "Optimization of NP-hard Scheduling Problems by Developing Timing Algorithms and Parallelization / Abhishek Awasthi ; Oliver Kramer, Jörg Lässig." Oldenburg : BIS der Universität Oldenburg, 2016. http://d-nb.info/1123210772/34.
Full textFallgren, Mikael. "Optimization of Joint Cell, Channel and Power Allocation in Wireless Communication Networks." Doctoral thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-40274.
Full textFinancial support by the Swedish Foundation for Strategic Research (SSF) QC 20110915
Eberle, Stefan. "A Polynomial Algorithm for a NP-hard to solve Optimization Problem." Diss., lmu, 2009. http://nbn-resolving.de/urn:nbn:de:bvb:19-99427.
Full textPokorný, Pavel. "Využití optimalizace v řízení výroby." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2008. http://www.nusl.cz/ntk/nusl-221771.
Full textSultanova, Nargiz. "A class of Increasing Positively Homogeneous functions for which global optimization problem is NP-hard." University of Ballarat, 2009. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/16160.
Full textMaster of Mathematical Sciences (Research)
Bonotto, Edison Luiz. "Otimização por Nuvem de Partículas e Busca Tabu para Problema da Diversidade Máxima." Universidade Federal da Paraíba, 2017. http://tede.biblioteca.ufpb.br:8080/handle/tede/9036.
Full textMade available in DSpace on 2017-06-29T14:15:20Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5) Previous issue date: 2017-01-31
The Maximu m Diversity Problem (MDP) is a problem of combinatorial optimization area that aims to select a pre-set number of elements in a given set so that a sum of the differences between the selected elements are greater as possible. MDP belongs to the class of NP-Hard problems, that is, there is no known algorithm that solves in polynomial time accurately. Because they have a complexity of exponential order, require efficient heuristics to provide satisfactory results in acceptable time. However, heuristics do not guarantee the optimality of the solution found. This paper proposes a new hybrid approach for a resolution of the Maximum Diversity Problem and is based on the Particle Swarm Optimization (PSO) and Tabu Search (TS) metaheuristics, The algorithm is called PSO_TS. The use of PSO_TS achieves the best results for known instances testing in the literature, thus demonstrating be competitive with the best algorithms in terms of quality of the solutions.
O Problema da Diversidade Máxima (MDP) é um problema da área de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível. O MDP pertence a classe de problemas NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heurísticas eficientes que forneçam resultados satisfatórios em tempos aceitáveis. Entretanto, as heurísticas não garantem otimalidade da solução encontrada. Este trabalho propõe uma nova abordagem híbrida para a resolução do Problema da Diversidade Máxima e está baseada nas meta-heurísticas de Otimização por Nuvem de Partículas (PSO) e Busca Tabu(TS). O algoritmo foi denominado PSO_TS. Para a validação do método, os resultados encontrados são comparados com os melhores existentes na literatura.
Book chapters on the topic "NP-Hard optimization problems"
Du, Ding-Zhu, Panos Pardalos, Xiaodong Hu, and Weili Wu. "NP-Hard Problems and Approximation Algorithms." In Introduction to Combinatorial Optimization, 199–257. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-10596-8_8.
Full textWoeginger, Gerhard J. "Exact Algorithms for NP-Hard Problems: A Survey." In Combinatorial Optimization — Eureka, You Shrink!, 185–207. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-36478-1_17.
Full textdos Santos Leal, Liara Aparecida, Dalcidio Moraes Claudio, Laira Vieira Toscani, and Paulo Blauth Menezes. "A Categorical Approach to NP-Hard Optimization Problems." In Computer Aided Systems Theory - EUROCAST 2003, 62–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-45210-2_7.
Full textCai, Liming, David Juedes, and Iyad Kanj. "The Inapproximability of Non NP-hard Optimization Problems." In Algorithms and Computation, 438–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-49381-6_46.
Full textSahai, Tuhin. "Dynamical Systems Theory and Algorithms for NP-hard Problems." In Advances in Dynamics, Optimization and Computation, 183–206. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-51264-4_8.
Full textHåstad, J. "Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?" In Automata, Languages and Programming, 235. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-45022-x_20.
Full textCohen, Aviad, Alexander Nadel, and Vadim Ryvchin. "Local Search with a SAT Oracle for Combinatorial Optimization." In Tools and Algorithms for the Construction and Analysis of Systems, 87–104. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72013-1_5.
Full textUma, R. N., and Joel Wein. "On the Relationship Between Combinatorial and LP-Based Approaches to NP-Hard Scheduling Problems." In Integer Programming and Combinatorial Optimization, 394–408. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-69346-7_30.
Full textKarpinski, Marek. "Polynomial time approximation schemes for some dense instances of NP-hard optimization problems." In Randomization and Approximation Techniques in Computer Science, 1–14. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/3-540-63248-4_1.
Full textGupta, Moha, Puneet Garg, and Prerna Agarwal. "Ant Colony Optimization Technique in Soft Computational Data Research for NP-Hard Problems." In Artificial Intelligence for a Sustainable Industry 4.0, 197–211. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-77070-9_12.
Full textConference papers on the topic "NP-Hard optimization problems"
Murthy, Garimella Rama. "Optimization of Quadratic Forms: NP Hard Problems: Neural Networks." In 2013 International Symposium on Computational and Business Intelligence (ISCBI). IEEE, 2013. http://dx.doi.org/10.1109/iscbi.2013.51.
Full textAbdelhafiez, Ehab A., and Fahd A. Alturki. "A new optimization algorithm for solving NP-hard problems." In 2010 2nd International Conference on Mechanical and Electrical Technology (ICMET). IEEE, 2010. http://dx.doi.org/10.1109/icmet.2010.5598491.
Full textWeissenberg, Julien, Hayko Riemenschneider, Ralf Dragon, and Luc Van Gool. "Dilemma First Search for effortless optimization of NP-hard problems." In 2016 23rd International Conference on Pattern Recognition (ICPR). IEEE, 2016. http://dx.doi.org/10.1109/icpr.2016.7900285.
Full textBabicz, Dora, Attila Tihanyi, Miklos Koller, Csaba Rekeczky, and Andras Horvath. "Simulation of an Analogue Circuit Solving NP-Hard Optimization Problems." In 2019 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2019. http://dx.doi.org/10.1109/iscas.2019.8702694.
Full textShafransky, Yakov M., T.-C. Edwin Cheng, and C.-T. Daniel Ng. "An approach for proving the NP-hardness of optimization problems with hard computable objectives." In Workshop on dynamic scheduling problems. Polish Mathematical Society, 2016. http://dx.doi.org/10.14708/isbn.978-83-937220-7-5p75-78.
Full textSavsani, Vimal, Poonam Savsani, and Prashant Arya. "Effect of Applying Advanced Optimization Techniques for the One-Dimensional Cutting Stock Problem." In ASME 2014 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2014. http://dx.doi.org/10.1115/imece2014-36095.
Full textZhu, Weihang, James Curry, Anjali Mishra, and Victor Zaloom. "Sequence Dependent Parallel Machine Scheduling Using Parallel Ant Colony Optimization With Graphics Hardware Acceleration." In ASME 2009 International Manufacturing Science and Engineering Conference. ASMEDC, 2009. http://dx.doi.org/10.1115/msec2009-84145.
Full textBiswas, Arpan, and Christopher Hoyle. "A Literature Review: Solving Constrained Non-Linear Bi-Level Optimization Problems With Classical Methods." In ASME 2019 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/detc2019-97192.
Full textQuan, Ning, and Harrison Kim. "A Tight Upper Bound for Grid-Based Wind Farm Layout Optimization." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59712.
Full textNeumann, Frank, and Carsten Witt. "Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables." 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/665.
Full text