Dissertations / Theses on the topic 'NP-complexity'
To see the other types of publications on this topic, follow the link: NP-complexity.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 45 dissertations / theses for your research on the topic 'NP-complexity.'
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.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Sempolinski, Peter. "Automatic Solutions of Logic Puzzles." Thesis, Boston College, 2009. http://hdl.handle.net/2345/690.
Full textAbstract:
Thesis advisor: Howard StraubingThe use of computer programs to automatically solve logic puzzles is examined in this work. A typical example of this type of logic puzzle is one in which there are five people, with five different occupations and five different color houses. The task is to use various clues to determine which occupation and which color belongs to each person. The clues to this type of puzzle often are statements such as, ''John is not the barber,'' or ''Joe lives in the blue house.'' These puzzles range widely in complexity with varying numbers of objects to identify and varying numbers of characteristics that need to be identified for each object. With respect to the theoretical aspects of solving these puzzles automatically, this work proves that the problem of determining, given a logic puzzle, whether or not that logic puzzle has a solution is NP-Complete. This implies, provided that P is not equal to NP, that, for large inputs, automated solvers for these puzzles will not be efficient in all cases. Having proved this, this work proceeds to seek methods that will work for solving these puzzles efficiently in most cases. To that end, each logic puzzle can be encoded as an instance of boolean satisfiability. Two possible encodings are proposed that both translate logic puzzles into boolean formulas in Conjunctive Normal Form. Using a selection of test puzzles, a group of boolean satisfiability solvers is used to solve these puzzles in both encodings. In most cases, these simple solvers are successful in producing solutions efficiently
Thesis (BS) — Boston College, 2009
Submitted to: Boston College. College of Arts and Sciences
Discipline: College Honors Program
Discipline: Computer Science
2
Simone, James Nicholas. "NP user interface modeling." Diss., Online access via UMI:, 2009.
Find full text
3
Ringh, Emil. "Low complexity algorithms for faster-than-Nyquistsign : Using coding to avoid an NP-hard problem." Thesis, KTH, Optimeringslära och systemteori, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-136936.
Full textAbstract:
This thesis is an investigation of what happens when communication links are pushed towards their limits and the data-bearing-pulses are packed tighter in time than previously done. This is called faster-than-Nyquist (FTN) signaling and it will violate the Nyquist inter-symbol interference criterion, implying that the data-pulsesare no longer orthogonal and thus that the samples at the receiver will be dependent on more than one of the transmitted symbols. Inter-symbol interference (ISI) has occurred and the consequences of it are studied for the AWGN-channel model. Here it is shown that in order to do maximum likelihood estimation on these samples the receiver will face an NP-hard problem. The standard algorithm to make good estimations in the ISI case is the Viterbi algorithm, but applied on a block with N bits and interference among K bits thecomplexity is O(N *2K), hence limiting the practical applicability. Here, a precoding scheme is proposed together with a decoding that reduce the estimation complexity. By applying the proposed precoding/decoding to a data block of length N the estimation can be done in O(N2) operations preceded by a single off-line O(N3) calculation. The precoding itself is also done in O(N2)operations, with a single o ff-line operation of O(N3) complexity. The strength of the precoding is shown in simulations. In the first it was tested together with turbo codes of code rate 2/3 and block lengthof 6000 bits. When sending 25% more data (FTN) the non-precoded case needed about 2.5 dB higher signal-to-noise ratio (SNR) to have the same error rate as the precoded case. When the precoded case performed without any block errors, the non-precoded case still had a block error rate almost equal to 1. We also studied the scenario of transmission with low latency and high reliability. Here, 600 bits were transmitted with a code rate of 2/3, and hence the target was to communicate 400 bits of data. Applying FTN with doublepacking, that is transmitting 1200 bits during the same amount of time, it was possible to lower the code rate to 1/3 since only 400 bits of data was to be communicated. This technique greatly improves the robustness. When the FTN case performed error free, the classical Nyquist case still had a block error rate of 0.19. To reach error free performance the Nyquist case needed 1.25 dB higher SNR compared to the precoded FTN case with lower code rate.Detta examensarbete handlar om vad som händer då kommunikationskanaler pressas till sin gräns och pulserna som bär data packas tätare i tiden. Detta kallas snabbare-än-Nyquist (FTN) och kommer att bryta mot Nyquists kriterium för intersymbolinterferens, vilket innebär att de databärande pulserna inte längre kommer vara ortogonala och att signalsamplen kommer vara beroende av mer än en skickad symbol. Det uppstår intersymbolinterferens (ISI) och dess konsekvenser studeras inom kanalmodellen AWGN. Vi visar att göra en maximum likelihood uppskattning baserat på dessa data är ett NP-svårt problem. Normalt används Viterbi algoritmen när man har ISI, men den har exponentiell komplexitet. På ett block med N symboler och interferens i storleken K symboler är komplexiteten O(N*2K) vilket gör att algoritmen är svår att använda i praktiska fall. Istället så föreslås en förkodning, som tillsammans med en avkodning reducerar komplexiteten. Kodningen appliceras blockvis och på ett block med N symboler är komplexiteten O(N2) för kodning/avkodning. Denna måste i båda fall föregås av en O(N3) beräkning, som dock behöver göras endast en gång. Simuleringar visar den föreslagna kodningens fördelar. I den första simuleringen testades den ihop med turbokodning med blocklängd på 6000 bitar och en kodningsgrad på 2/3. När FTN användes för att skicka 25% mer data krävdes det cirka 2.5 dB högre signal-till-brus-förhållande (SNR) för att den icke förkodade signalen skulle ha samma felfrekvens som den förkodade. När det förkodade fallet presterade felfritt gjorde det oförkodade fel på nästan alla block. Ett annat scenario som testades var det med korta koder, liten fördröjning och hög robusthet. I detta scenario skickades 600 bitar med en kodningsgrad på 2/3, alltså 400 bitar ren data. Genom att använda FTN med en dubbel packningsgrad, vilket innebär att 1200 bitar skickades under samma tid, var det möjligt att sänka kodningsgraden till 1/3, eftersom det bara var 400 bitar ren data som skulle överföras. Detta ökad robustheten i systemet ty då FTN fallet gjorde felfritt hade det klassiska Nyquist fallet fortfarande en felfrekvens på 0.19 för sina block. Det krävdes 1.25 dB högre SNR för Nyquist fallet att bli felfritt jämfört med FTN och lägre kodningsgrad.
4
Maji, Nabanita. "An Interactive Tutorial for NP-Completeness." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/52973.
Full textAbstract:
A Theory of Algorithms course is essential to any Computer Science curriculum at both the undergraduate and graduate levels. It is also considered to be difficult material to teach or to learn. In particular the topics of Computational Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students.
Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to the best of our knowledge, the instructional material available for NP-Completeness is mostly static and textual, which does little to alleviate the complexity of the topic.
Our aim is to improve the pedagogy of NP-Completeness by providing intuitive, interactive, and easy-to-understand visualizations for standard NP Complete problems, reductions, and proofs. In this thesis, we present a set of visualizations that we developed using the OpenDSA framework for certain NP-Complete problems. Our paradigm is a three step process. We first use an AV to illustrate a particular NP-Complete problem. Then we present an exercise to provide a first-hand experience with attempting to solve a problem instance. Finally, we present a visualization of a reduction as a part of the proof for NP-Completeness.
Our work has been delivered as a collection of modules in OpenDSA, an interactive eTextbook system developed at Virginia Tech. The tutorial has been introduced as a teaching supplement in both a senior undergraduate and a graduate class. We present an analysis of the system use based on records of online interactions by students who used the tutorial. We also present results from a survey of the students.Master of Science
5
Huang, Xiuzhen. "Parameterized complexity and polynomial-time approximation schemes." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1446.
Full textAbstract:
According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to find good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small.
In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems.
We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the first systematic investigation of this new but important approximation class.
We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function
f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices.
We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the first time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.
6
Beyersdorff, Olaf. "Disjoint NP-pairs and propositional proof systems." Doctoral thesis, [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=981087590.
Full text
7
Ono, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.
Find full text
8
Cornet, Alexis. "Algorithmes et résultats de complexité pour des problèmes de graphes avec contraintes additionnelles." Thesis, Université Clermont Auvergne (2017-2020), 2018. http://www.theses.fr/2018CLFAC034/document.
Full textAbstract:
Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédentsDomination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems
9
Serédi, Silvester. "Evoluční algoritmy v úloze booleovské splnitelnosti." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236224.
Full textAbstract:
The goal of this Master's Thesis is finding a SAT solving heuristic by the application of an evolutionary algorithm. This thesis surveys various approaches used in SAT solving and some variants of evolutionary algorithms that are relevant to this topic. Afterwards the implementation of a linear genetic programming system that searches for a suitable heuristic for SAT problem instances is described, together with the implementation of a custom SAT solver which expoloits the output of the genetic program. Finally, the achieved results are summarized.
10
Fallgren, 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 textAbstract:
In this thesis we formulate joint cell, channel and power allocation problems within wireless communication networks. The objectives are to maximize the user with mini- mum data throughput (Shannon capacity) or to maximize the total system throughput, referred to as the max-min and max-sum problem respectively. The complexity is stud- ied together with proposed optimization- and heuristic-based approaches. In the first paper an overall joint cell, channel and power allocation max-min prob- lem is formulated. We show that the decision problem is NP-hard and that the op- timization problem is not approximable unless P is equal to NP, for instances with a sufficiently large number of channels. Further, it follows that for a feasible binary cell and channel allocation, the remaining continuous power allocation optimization problem is still not approximable unless P is equal to NP. In addition, it is shown that first-order optimality conditions give global optimum of the single channel power al- location optimization problem, although the problem is in general not convex. In the following two papers heuristics for solving the overall problem are proposed. In the second paper we consider the single channel problem with convex combinations of the max-min and the max-sum objective functions. This variable utility provides the ability of tuning the amount of fairness and total throughput. The third paper investi- gates the multiple channel setting. On a system with three cells, eight mobile users and three channels, we perform an exhaustive search over feasible cell and channel alloca- tions. The exhaustive search is then compared to the less computationally expensive heuristic approaches, presenting potential earnings to strive for. A conclusion is that several of the proposed heuristics perform very well. The final paper incorporates fixed relay stations into the overall joint cell, channel and power allocation max-min problem. The complexity is inherited from the formula- tion without relay stations. Further, we propose a heuristic channel allocation approach that shows good performance, compared to an optimization based approach, in numer- ical simulations on the relay setting.Financial support by the Swedish Foundation for Strategic Research (SSF) QC 20110915
11
Wenner, Cenny. "Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction." Doctoral thesis, Stockholms universitet, Numerisk analys och datalogi (NADA), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-107685.
Full textAbstract:
Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). Most CSPs are NP-hard to solve optimally and we turn to approximations - a solution is said to be a factor-c approximation if its satisfies at least c times the optimal number of constraints. This thesis presents new results on the approximation limits of CSPs in various settings. In ordering CSPs, one is given constraints which specify the relative order of items, and the objective is order the items so as to satisfy as many constraints as possible. We give improved approximation hardness results for two classical problems: it is NP-hard to approximate Maximum Acyclic Subgraph with a factor better than 14/15 and Maximum Betweenness with a factor better than 1/2. We present ordering problems which are NP-hard to approximate better than random assignments, and that there are ordering problems arbitrarily hard to approximate. Next, Gaussian elimination can efficiently find exact solutions for satisfiable collections of so-called parity constraints. We show that whenever constraints accept at least one assignment in addition to a parity, then the problem is NP-hard to approximate better than random assignments. Finally, we study the uselessness property which basically states that if one is given a collection where almost all constraints are simultaneously satisfiable and one is permitted to relax the constraints to accept or reject additional assignments, then it is still NP-hard to find solutions noticeably better than random assignments. We consider the setting where all variables appear unnegated and provide the first examples of non-trivially useless predicates assuming only P != NP.Kombinatoriska optimering inkluderar naturliga uppgifter såsom att hitta den snabbaste vägen till sitt arbetet, att schemalägga jobb hos specialister, eller att placera hållplatser för att minimera resenärers restid.Vi begränsar vi oss till de problem i vilket man ges en samling vilkor på variablermed målet att hitta en tilldelning av variablerna uppfyllandes så många som möjligt av vilkoren;så kallade Vilkorsuppfyllningsproblem (eng: Constraint Satisfaction Problems, CSPs).De flesta CSPs är NP-svåra att lösa optimalt och vi beaktar istället approximationer. Specifikt kallas, för 0 <= c <= 1, en lösning för en faktor-c approximation om antalet vilkor uppfyllda av lösningen är minst cgånger det största antalet uppfyllda av någon läsning. Denna avhandling består av tre artiklar som presenterar nya resultat begränsande hurpass väl man kan approximera CSPs i diverse situationer.För paritetsvilkor är en samling konsistenta vilkor enkla att lösa genom Gausselimination. Vi visar att för samtliga vilkor som uppfylls av en paritet och åtminstonde en ytterliggare tilldelning så är det inte bara NP-svårt at lösa utan till och med att ge en icke-trivial approximation.Oanvändarbarhet är en stark svårighetsegenskap som i princip säger att det är NP-svårt att ge icke-triviala approximationer även när man gemensamt för alla vilkor får ändra vad som uppfyller dem eller inte. Vi ger de första exemplen på icke-trivialt oanvändbara vilkor utan negationer betingat endast på P != NP.Vi visar på approximerbarhet för diverse ordningsvilorsproblem. I dessa ges man vilkor på hur objekt ska vara ordnade relativt varandra och målet är att hitta en ordning som uppfyller så många av vilkoren som möjligt. Vi ger bättre svårighetsresultat för de två mest välkända ordningsproblem, visar att det finns problem där det är NP-svårt att approximera bättre än triviala strategier, och att det finns ordningsproblem där godtyckligt dåliga approximationsgarantier är NP-svåra.
NADA är en delad institution mellan SU och KTH där senare nu kallar den CSC.
ApproxNP
12
Glorieux, Antoine. "Optimizing the imbalances in a graph." Thesis, Evry, Institut national des télécommunications, 2017. http://www.theses.fr/2017TELE0011/document.
Full textAbstract:
Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomialThe imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time
13
Зінченко, Людмила Вікторівна. "Інформаційна рекомендаційна система в сфері освітніх послуг." Master's thesis, КПІ ім. Ігоря Сікорського, 2019. https://ela.kpi.ua/handle/123456789/31409.
Full textAbstract:
Магістерська дисертація: 85 с., 7 рис., 23 табл., 29 джерел, 1 додаток. Актуальність. Сьогодні є актуальною онлайн-освіта. На жаль, в Україні
мало альтернативних ресурсів, де б можна було отримати онлайн-допомогу з різних предметних областей. Все більше учнів, студентів, людей, які перекваліфіковуючись чи просто хочуть розвиватися шукають способи отримати нові теоретичні знання та практичні навички онлайн. Надзвичайно важко самостійно опанувати великий потік інформації, яку б предметну область не вивчали учні, і тому необхідна допомога професіоналів. Тож великою цінністю представляється функціонал щодо розкладу. Для вирішення проблеми, як реалізувати цю частину функціоналу, буде поставлена і розв’язана нова математична задача, яка дасть можливість і підґрунтя вирішувати подібні проблеми.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на філії кафедри автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» у рамках науково-дослідницької теми Інституту кібернетики ім. В. М. Глушкова НАН України ВФ.180.11 «Розробити математичний апарат, орієнтований на створення інтелектуальних інформаційних технологій розв'язування проблем комбінаторної оптимізації та інформаційної безпеки» (2017-2021 рр.), що виконується за Постановою бюро Відділення інформатики НАН України від 23.06.2016 р. № 2.
Мета роботи – підвищення якості інформування потенційних споживачів та інтелектуалізація процесів надання освітніх послуг онлайн, шляхом розробки оригінального програмно-алгоритмічного забезпечення та реалізації його у вигляді спеціалізованої програмної системи.
Для досягнення мети необхідно виконати наступні завдання:
виконати огляд існуючих постановок задач у сфері освіти; виконати огляд існуючих методів розв’язання задач складання розкладу;
здійснити порівняльний аналіз різних методів та моделей та класифікувати їх;
формалізувати задачу складання розкладу для менторів та учнів;
розробити алгоритм локального пошуку і мурашиний алгоритм;
виконати аналіз експериментальних досліджень;
розробити програмне забезпечення для надання послуг у сфері освіти;
розробити стартап-проект.
Об’єкт дослідження – процес побудови розкладу для менторів і учнів, який задовольняє певним критеріям.
Предмет дослідження – методи та моделі задач комбінаторної оптимізації в задачах теорії розкладів.
Наукова новизна одержаних результатів полягає у постановці та аналізі нової задачі, а також у дослідження методів розв’язання цієї задачі, розробці методів локального пошуку та мурашиного алгоритму для поставленої задачі складання розкладу онлайн занять.
Публікації. Матеріали роботи опубліковані в міжнародних наукових журналах «INNOVATIVE SOLUTIONS IN MODERN SCIENCE» (№6 (33), 2019), та «POLISH JOURNAL OF SCIENCE» (№16, 2019), а також у тезах міжнародних науково-практичних конференцій «Математичне та імітаційне моделювання систем» (МОДС 2019), «Інформаційні системи та технології управління» (ІСТУ-2019).Master's thesis: 85 p., 7 figures, 23 tables, 29 sources, 1 applications. Relevance: Online education is relevant today. Unfortunately, there are few alternative resources in Ukraine where online help can be obtained from various subject areas. More and more students from schools and universities, people who are retraining or just looking to develop are looking for ways to gain new theoretical knowledge and practical skills online. It is extremely difficult to master a large flow of information on your own, whatever the subject area is not learned by students, and therefore requires the help of professionals. Therefore, scheduling functionality is of great value. To solve the problem of how to implement this part of the functionality, a new mathematical problem will be posed and solved, which will give the opportunity and the basis for solving such problems. Connection of the thesis with scientific programs, plans, topics. The thesis was written at the branch of The Department of Computer-aided management and data processing systems of the National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» at the V. M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine under the topic VF.180.11 «To develop a mathematical apparatus focused on the creation of intelligent information technologies for solving combinatorial optimization and information security problems» (2017-2021 biennium), which is executed by the Resolution of the Bureau of Informatics of the National Academy of Sciences of Ukraine from 23.06.2016 р. № 2. The purpose of the study is improving the quality of informing potential consumers and intellectualizing the processes of providing educational services online, by developing original software and algorithmic software and implementing it in the form of a specialized software system.. To achieve this goal, you must complete the following tasks: − review the existing formulations of educational tasks; − review existing methods for scheduling tasks; − carry out comparative analysis of different methods and models and classify them; − formalize the timetable for mentors and students; − develop a local search algorithm and an ant algorithm; − carry out the analysis of experimental studies; − develop software to provide educational services; − develop a startup project. The object of study is a process for scheduling mentors and students that meets certain criteria. The subject of study is methods and models of combinatorial optimization problems in scheduling theory problems. The scientific novelty of the results is the formulation and analysis of a new task, as well as the study of methods for solving this problem, the development of methods of local search and ant algorithm for the task of scheduling online classes. Publications. Work materials have been published in the international scientific journals «INNOVATIVE SOLUTIONS IN MODERN SCIENCE» (№6 (33), 2019) and «POLISH JOURNAL OF SCIENCE» (№16, 2019), as well as in theses of international scientific and practical conferences «Mathematical and systems simulation» (MODS 2019), «Information systems and control technologies» (ISTU-2019).
14
Nilsson, Mikael. "Spanneröar och spannervägar." Thesis, Institutionen för datavetenskap, Naturvetenskapliga fakulteten, Lunds universitet, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-93331.
Full textAbstract:
In this Master Thesis the possibility to efficiently divide a graph into spanner islands is examined. Spanner islands are islands of the graph that fulfill the spanner condition, that the distance between two nodes via the edges in the graph cannot be too far, regulated by the stretch constant, compared to the Euclidian distance between them. In the resulting division the least number of nodes connecting to other islands is sought-after. Different heuristics are evaluated with the conclusion that for dense graphs a heuristic using MAX-FLOW to divide problematic nodes gives the best result whereas for sparse graphs a heuristic using the single-link clustering method performs best. The problem of finding a spanner path, a path fulfilling the spanner condition, between two nodes is also investigated. The problem is proven to be NP-complete for a graph of size n if the spanner constant is greater than n^(1+1/k)*k^0.5 for some integer k. An algorithm with complexity O(2^(0.822n)) is given. A special type of graph where all the nodes are located on integer locations along the real line is investigated. An algorithm to solve this problem is presented with a complexity of O(2^((c*log n)^2))), where c is a constant depending only on the spanner constant. For instance, the complexity O(2^((5.32*log n)^2))) can be reached for stretch 1.5.I det här magisterarbetet undersöks om det är möjligt att på ett effektivt sätt dela upp en graf i spanneröar, dvs. öar som uppfyller spanneregenskapen som består i att avståndet mellan två noder via grafens bågar inte får vara för stort i förhållande till det euklidiska avståndet mellan noderna. Att hitta en uppdelning som skapar så få kontaktpunkter mellan öarna som möjligt eftersöks. Ett antal heuristiker testas och utvärderas med resultatet att en heuristik som använder sig av MAX-FLOW för att dela upp noder som bryter mot spannervillkoret presterar bäst för täta grafer medan en heuristik av typ single-link clustering presterar bäst för glesa grafer. I arbetet visas att problemet att finna en spannerväg, en väg där noderna som passeras uppfyller spannervillkoret, mellan två noder i en graf av storlek n är NP-komplett om spannerkonstanten är större än n^(1+1/k)*k^0.5 för något heltal k. En algoritm för att hitta spannervägar med komplexiteten O(2^(0.822n)) presenteras. Ett specialproblem där grafen ligger längs tallinjen och bara har noder på heltalspunkter studeras slutligen och här konstrueras en algoritm med komplexiteten O(2^((c*log n)^2))) där c är en konstant som beror på spannerkonstanten. Till exempel nås O(2^((5.32*log n)^2))) för stretch 1.5.
15
Foucaud, Florent. "Aspects combinatoires et algorithmiques des codes identifiants dans les graphes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2012. http://tel.archives-ouvertes.fr/tel-00766138.
Full textAbstract:
Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.
16
Sayadi, Mohamed Yosri. "Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0316.
Full textAbstract:
Moon et Moser ont prouvé que le nombre maximum des ensembles stables maximaux dans un graphe de n sommets est au plus 3^{n/3}. Cette borne, appelée borne supérieure, est stricte vu l’existence d’une famille des graphes avec un tel nombre appelée borne inférieure. Au contraire de l’énumération des ensembles stables maximaux, avoir deux bornes qui se qui se coïncident n’est pas évident du tout. Et c’est assez courant dans l’énumération « input-sensitive » d’avoir un grand écart. Ce problème concerne même les ensembles les plus classiques comme les ensembles dominants minimaux où le meilleur algorithme connu pour énumérer ces ensembles est en O(1.7159^n) et la meilleure borne inférieure connue est seulement 1.5704^n. Durant cette thèse, on a proposé un algorithme « Mesurer pour Conquérir » pour énumérer tous les ensembles dominants minimaux dans les graphes cordaux en O(1.5048^n). On a étudié aussi l’énumération des ensembles dominants connexes minimaux et les ensembles irredondants maximaux qui sont très proches des ensembles dominants minimaux. On a proposé un algorithme d’énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes en O(1.7254^n). On a conçu aussi des algorithmes d’énumération des ensembles irredondants maximaux dans les graphes cordaux, les graphes d’intervalles et les forêts en O(1.7549^n), O(1.6957^n ) et O(1.6181^n) respectivement au lieu de l’algorithme trivial en O*(2^n). On a proposé aussi comme une borne inférieure une famille de forêts avec Omega(1.5292^n) ensembles irredondants maximaux. Dans le cas des cographes, l'écart entre les deux bornes est réduit à néant en montrant que le nombre maximum de ces ensembles est Theta(15^{n/6}). Afin de varier, on a étudié un nouvel ensemble défini récemment : L’ensemble tropical connexe minimal. On a proposé une borne inférieure de 1.4961^n, mais sans réussir à améliorer la borne supérieure de 2^n. On a proposé des algorithmes d’énumération des ensembles tropicaux connexes minimaux dans les graphes cobipartis, les graphes d’intervalles et les graphes blocs en O*(3^{n/3}), O(1.8613^n) et O*(3^{n/3}) respectivement. On a établi une borne inférieure de 1.4766^n pour les graphes scindés et de 3^{n/3} pour les graphes cobipartis, les graphes d’intervalles et les graphes blocs. Finalement, comme perspective et pour attirer l’attention de la communauté sur l’énumération des ensembles dominants totaux minimaux, on a montré que le nombre maximum de ces ensembles est Ω(1.5848^n)Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound. Unlike the enumeration of maximal independent sets, having a tight bounds is not obvious at all. And it’s quite common in the “input-sensitive” enumeration to have a big gap. This problem concerns even the most studied sets as minimal dominating sets where the best known algorithm to enumerate those sets runs in time O(1.7159^n) and the best known lower bound is only 1.5704^n. During this thesis, we proposed a "Measure and Conquer" algorithm to enumerate all minimal dominating sets for chordal graphs in time O(1.5048^n). Minimal connected dominating sets and maximal irredundant sets, which are closely related to minimal dominating sets, were also studied. An enumeration algorithm of minimal connected dominating sets in convex bipartite graphs has been proposed with a running time in O(1.7254^n). Enumeration algorithms of maximal irredundant sets have also been given for chordal graphs, interval graphs, and forests in times O(1.7549^n), O(1.6957^n) and O(1.6181^n) respectively instead of the trivial algorithm in time O*(2^n). We complement these upper bounds by showing that there are forest graphs with Omega(1.5292^n) maximal irredundant sets. We proved also that every maximal irredundant set of a cograph is a minimal dominating set. This implies that the maximum number of those sets in cographs is Theta(15^{n/6}). Finally, to vary, we studied a new set has been defined recently: The minimal tropical connected set. A lower bound of 1.4961^n has been proposed but we failed to improve the upper bound of 2^n. Enumeration algorithms of minimal tropical connected sets have been given for cobipartite, interval and block graphs in times O*(3^{n/3}), O(1.8613^n) and O*(3^{n/3}) respectively. A lower bound of 1.4766^n for splits graphs and 3^{n/3} for cobipartite, interval graphs and block graphs have been provided. We proposed a new lower bound of 1.5848^n, as a perspective and in order to draw community attention to the maximum number of minimal total dominating sets
17
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
Full textAbstract:
Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielleThe problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied
18
Miček, David. "Genetické algoritmy." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-218215.
Full textAbstract:
This thesis presents description of Genetic algorithm. The description begins with theory of complexity and following basic theory of genetic algorithm. Next part explains the principle of all three tasks – travelling salesman problem, knapsack problem and evolution of algorithm for five-in-a-row. The main focus was on developing the algorithm for five-in-a-row. The results were tested with other similar algorithms from internet. In case of travelling salesman problem and knapsack problem, the results were compared with gradient optimization methods.
19
Ho, Yiu Yu. "Global secure sets of trees and grid-like graphs." Doctoral diss., University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4922.
Full textAbstract:
However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in (BDH07) for exactly this purpose. The non-empty set S is a secure set if every subset Xsubset of]S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In (BDH07), the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if for all] X subset of] S, vertical line]N (X) intersection] Svertical line] greater than or equal to] vertical line]N(X) - Svertical line] ((BDH07),Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N (S)= V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gamma subscript s](G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.; Let G = (V, E) be a graph and let S subset of] V be a subset of vertices. The set S is a defensive alliance if for all x element of] S, vertical line]N(x)intersection] Svertical line]greater than or equal to] vertical line]N(x) - Svertical line]. The concept of defensive alliances was introduced in (KHH04), primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, (FLG00) applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies for all] x element of] C, vertical line]N(x) intersection] Cvertical line] greater than] vertical line]N(x) - Cvertical line]. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended.ID: 030423421; System requirements: World Wide Web browser and PDF reader.; Mode of access: World Wide Web.; Thesis (Ph.D.)--University of Central Florida, 2011.; Includes bibliographical references (p. 206-210).
Ph.D.
Doctorate
Electrical Engineering and Computer Science
Engineering and Computer Science
20
Oliveira, Igor Carboni. "Complexidade computacional e o problema P vs NP." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275804.
Full textAbstract:
Orientador: Arnaldo Vieira MouraDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-16T09:31:55Z (GMT). No. of bitstreams: 1 Oliveira_IgorCarboni_M.pdf: 1109272 bytes, checksum: 3ab44664e4e0b862409cc8038c431a06 (MD5) Previous issue date: 2010
Resumo: A teoria de complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível. Esta dissertação oferece tanto uma introdução clássica ao tema, quanto uma exposição a diversos teoremas mais avançados, resultados recentes e problemas em aberto. Em particular, o método da diagonalização é discutido em profundidade. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia de tempo e de espaço (Hartmanis e Stearns [54, 104]). Apresentamos uma generalização desses resultados, obtendo como corolários os teoremas clássicos provados por Hartmanis e Stearns. Essa é a primeira vez que uma prova unificada desses resultados aparece na literatura
Abstract: Computational complexity theory is the field of theoretical computer science that aims to establish limits on the efficiency of algorithms. The main open question in computational complexity is the P vs NP problem. Intuitively, it states that, for several important computational problems, there is no algorithm that performs better than a trivial exhaustive search. We present here an introduction to the subject, followed by more recent and advanced results. In particular, the diagonalization method is discussed in detail. Although it is a classical technique in computational complexity, it is the only method that was able to separate strong complexity classes so far. Some of the most important results in computational complexity theory have been proven by diagonalization. In particular, Hartmanis and Stearns [54, 104] proved that, given more resources, one can solve more computational problems. These results are known as hierarchy theorems. We present a generalization of the deterministic hierarchy theorems, recovering the classical results proved by Hartmanis and Stearns as corollaries. This is the first time that such unified treatment is presented in the literature
Mestrado
Teoria da Computação
Mestre em Ciência da Computação
21
Colares, Rafael. "Exploring Combinatorial Aspects of the Stop Number Problem." Thesis, Université Clermont Auvergne (2017-2020), 2019. http://www.theses.fr/2019CLFAC050.
Full textAbstract:
Le Problème du Nombre d'Arrêts se présente dans la gestion d'un système de transport à la demande utilisant des véhicules électriques autonomes. Dans un tel système, une flotte de véhicules identiques parcourt un circuit prédéfini avec des stations fixes afin de desservir un ensemble de clients qui demandent un trajet entre une station d'origine et une station de destination. Notez que plusieurs clients peuvent partager les mêmes stations d'origine et/ou de destination. Le Problème du Nombre d'Arrêts consiste à affecter chaque demande à un véhicule de façon à ce qu'aucun véhicule ne soit surchargé. L'objectif est de minimiser le nombre d'arrêts effectués par la flotte de véhicules pour la collecte et la livraison des clients. Lorsque chaque client demande exactement une place dans un véhicule, le Problème du Nombre d'Arrêts est appelé Problème du Nombre d'Arrêts Unitaire. Dans cette thèse, le Problème du Nombre d'Arrêts Unitaire est traité comme un problème d'optimisation combinatoire.Tout d'abord, nous examinons la complexité du problème. D'une part, nous étudions certaines propriétés des solutions optimales et dérivons une série de cas particuliers dont la résolution peut être réalisée en temps polynomial. D'autre part, nous montrons que le Problème du Nombre d'Arrêts Unitaire est NP-Difficile même lorsqu'il est restreint au cas où chaque véhicule peut prendre au maximum deux clients à la fois et que le graphe induit par les demandes des clients est planaire bipartie. Ce résultat - qui répond positivement à une conjecture connue dans la littérature - est ensuite étendu à d'autres problèmes associés tels que le k-Edge Partitioning et le Traffic Grooming, améliorant ainsi leurs standards de complexité connus dans la littérature.Dans une deuxième partie, nous considérons une formulation de programmation linéaire en nombres entiers connue dans la littérature pour résoudre le Problème du Nombre d'Arrêts Unitaire. Une analyse préliminaire est effectuée afin de prouver la faiblesse de cette formulation. Par la suite, cette formulation est renforcée à l'aide d'une approche polyédrale. Nous fournissons une étude de faciale du polytope associée aux solutions de ce problème. De nouvelles inégalités valides sont introduites et les conditions nécessaires et suffisantes pour lesquelles elles définissent des facettes sont indiquées.Enfin, sur la base des résultats de l'approche polyédrale discutée, nous dérivons un nouvel algorithme de coupes et branchements efficace. Des fonctionnalités améliorant les performances de l’algorithme, telles que les méthodes de rupture de symétrie et l'élimination/relaxation des variables, sont également étudiées et mises en œuvre. Les résultats démontrent de manière convaincante la pertinence du renforcement des inégalités valides et donc de notre algorithme de coupes et branchementsThe Stop Number Problem arises in the management of a dial-a-ride system with small autonomous electric vehicles. In such a system, a fleet of identical capacitated vehicles travels along a predefined circuit with fixed stations in order to serve clients requesting for a ride from an origin station to a destination station. Notice that multiple clients may share the same origin and/or destination stations. The Stop Number Problem consists of assigning each client request to avehicle such that no vehicle gets overloaded. The goal is to minimize the number of times the fleet of vehicles stops for picking up or delivering clients. When every client requests for exactly one seat in a vehicle, Stop Number Problem is called Unit Stop Number Problem. In this thesis, Unit Stop Number Problem is addressed as a combinatorial-optimization problem.First, we investigate the complexity of such problem. On the one hand, we study some properties of optimal solutions and derive a series of particular cases that are shown to be solvable in polynomial time. On the other hand, we show that Unit Stop Number Problem is NP-Hard even when restricted to case where each vehicle can take at most two clients at once and the graph induced by the client requests is planar bipartite. Such result -- which positively answers a conjecture known in the literature -- is then extended to other related problems such as the k-Edge Partitioning and the Traffic Grooming problem, improving their respective state-of-the-art complexity standards.In a second part, we consider an integer-programming formulation known in the literature for solving the Unit Stop Number Problem. A preliminary analysis is conducted in order to prove the weakness of such formulation. Afterwards, such formulation is reinforced through a polyhedral approach. We provide a facial study of the polytope associated with the solutions of this problem. New valid inequalities are introduced and necessary and sufficient conditions for which they are facet-defining are given.Finally, based on the discussed polyhedral results, we derive a new efficient branch-and-cut algorithm. Performance boosting features such as symmetry breaking methods and variable elimination/relaxation are also investigated and implemented into the developed framework. Results convincingly demonstrate the strength of the reinforcing valid inequalities and therefore of our branch-and-cut algorithm
22
Brancotte, Bryan. "Agrégation de classements avec égalités : algorithmes, guides à l'utilisateur et applications aux données biologiques." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112184/document.
Full textAbstract:
L'agrégation de classements consiste à établir un consensus entre un ensemble de classements (éléments ordonnés). Bien que ce problème ait de très nombreuses applications (consensus entre les votes d'utilisateurs, consensus entre des résultats ordonnés différemment par divers moteurs de recherche...), calculer un consensus exact est rarement faisable dans les cas d'applications réels (problème NP-difficile). De nombreux algorithmes d'approximation et heuristiques ont donc été conçus. Néanmoins, leurs performances (en temps et en qualité de résultat produit) sont très différentes et dépendent des jeux de données à agréger. Plusieurs études ont cherché à comparer ces algorithmes mais celles-ci n’ont généralement pas considéré le cas (pourtant courant dans les jeux de données réels) des égalités entre éléments dans les classements (éléments classés au même rang). Choisir un algorithme de consensus adéquat vis-à-vis d'un jeu de données est donc un problème particulièrement important à étudier (grand nombre d’applications) et c’est un problème ouvert au sens où aucune des études existantes ne permet d’y répondre. Plus formellement, un consensus de classements est un classement qui minimise le somme des distances entre ce consensus et chacun des classements en entrés. Nous avons considérés (comme une grande partie de l’état-de-art) la distance de Kendall-Tau généralisée, ainsi que des variantes, dans nos études. Plus précisément, cette thèse comporte trois contributions. Premièrement, nous proposons de nouveaux résultats de complexité associés aux cas que l'on rencontre dans les données réelles où les classements peuvent être incomplets et où plusieurs éléments peuvent être classés à égalité. Nous isolons les différents « paramètres » qui peuvent expliquer les variations au niveau des résultats produits par les algorithmes d’agrégation (par exemple, utilisation de la distance de Kendall-Tau généralisée ou de variantes, d’un pré-traitement des jeux de données par unification ou projection). Nous proposons un guide pour caractériser le contexte et le besoin d’un utilisateur afin de le guider dans le choix à la fois d’un pré-traitement de ses données mais aussi de la distance à choisir pour calculer le consensus. Nous proposons finalement une adaptation des algorithmes existants à ce nouveau contexte. Deuxièmement, nous évaluons ces algorithmes sur un ensemble important et varié de jeux de données à la fois réels et synthétiques reproduisant des caractéristiques réelles telles que similarité entre classements, la présence d'égalités, et différents pré-traitements. Cette large évaluation passe par la proposition d’une nouvelle méthode pour générer des données synthétiques avec similarités basée sur une modélisation en chaîne Markovienne. Cette évaluation a permis d'isoler les caractéristiques des jeux de données ayant un impact sur les performances des algorithmes d'agrégation et de concevoir un guide pour caractériser le besoin d'un utilisateur et le conseiller dans le choix de l'algorithme à privilégier. Une plateforme web permettant de reproduire et étendre ces analyses effectuée est disponible (rank-aggregation-with-ties.lri.fr). Enfin, nous démontrons l'intérêt d'utiliser l'approche d'agrégation de classements dans deux cas d'utilisation. Nous proposons un outil reformulant à-la-volé des requêtes textuelles d'utilisateur grâce à des terminologies biomédicales, pour ensuite interroger de bases de données biologiques, et finalement produire un consensus des résultats obtenus pour chaque reformulation (conqur-bio.lri.fr). Nous comparons l'outil à la plateforme de références et montrons une amélioration nette des résultats en qualité. Nous calculons aussi des consensus entre liste de workflows établie par des experts dans le contexte de la similarité entre workflows scientifiques. Nous observons que les consensus calculés sont très en accord avec les utilisateurs dans une large proportion de casThe rank aggregation problem is to build consensus among a set of rankings (ordered elements). Although this problem has numerous applications (consensus among user votes, consensus between results ordered differently by different search engines ...), computing an optimal consensus is rarely feasible in cases of real applications (problem NP-Hard). Many approximation algorithms and heuristics were therefore designed. However, their performance (time and quality of product loss) are quite different and depend on the datasets to be aggregated. Several studies have compared these algorithms but they have generally not considered the case (yet common in real datasets) that elements can be tied in rankings (elements at the same rank). Choosing a consensus algorithm for a given dataset is therefore a particularly important issue to be studied (many applications) and it is an open problem in the sense that none of the existing studies address it. More formally, a consensus ranking is a ranking that minimizes the sum of the distances between this consensus and the input rankings. Like much of the state-of-art, we have considered in our studies the generalized Kendall-Tau distance, and variants. Specifically, this thesis has three contributions. First, we propose new complexity results associated with cases encountered in the actual data that rankings may be incomplete and where multiple items can be classified equally (ties). We isolate the different "features" that can explain variations in the results produced by the aggregation algorithms (for example, using the generalized distance of Kendall-Tau or variants, pre-processing the datasets with unification or projection). We propose a guide to characterize the context and the need of a user to guide him into the choice of both a pre-treatment of its datasets but also the distance to choose to calculate the consensus. We finally adapt existing algorithms to this new context. Second, we evaluate these algorithms on a large and varied set of datasets both real and synthetic reproducing actual features such as similarity between rankings, the presence of ties and different pre-treatments. This large evaluation comes with the proposal of a new method to generate synthetic data with similarities based on a Markov chain modeling. This evaluation led to the isolation of datasets features that impact the performance of the aggregation algorithms, and to design a guide to characterize the needs of a user and advise him in the choice of the algorithm to be use. A web platform to replicate and extend these analyzes is available (rank-aggregation-with-ties.lri.fr). Finally, we demonstrate the value of using the rankings aggregation approach in two use cases. We provide a tool to reformulating the text user queries through biomedical terminologies, to then query biological databases, and ultimately produce a consensus of results obtained for each reformulation (conqur-bio.lri.fr). We compare the results to the references platform and show a clear improvement in quality results. We also calculate consensus between list of workflows established by experts in the context of similarity between scientific workflows. We note that the computed consensus agree with the expert in a very large majority of cases
23
Jurčík, Lukáš. "Evoluční algoritmy při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2014. http://www.nusl.cz/ntk/nusl-224447.
Full textAbstract:
This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.
24
Menadjelia, Nardjes. "Vers le recouvrement automatique dans la composition de services WEB basée protocole." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2013. http://tel.archives-ouvertes.fr/tel-00874865.
Full textAbstract:
Dans une composition de services Web basée protocole, un ensemble de services composants se collaborent pour donner lieu à un service Composite. Chaque service est représenté par un automate à états finis (AEF). Au sein d'un AEF, chaque transition exprime l'exécution d'une opération qui fait avancer le service vers un état suivant. Une exécution du composite correspond à une séquence de transitions où chacune est déléguée à un des composants. Lors de l'exécution du composite, un ou plusieurs composants peuvent devenir indisponibles. Ceci peut produire une exécution incomplète du composite, et de ce fait un recouvrement est nécessaire. Le recouvrement consiste à transformer l'exécution incomplète en une exécution alternative ayant encore la capacité d'aller vers un état final. La transformation s'effectue en compensant certaines transitions et exécutant d'autres. Cette thèse présente une étude formelle du problème de recouvrement dans une composition de service Web basée protocole. Le problème de recouvrement consiste à trouver une meilleure exécution alternative parmi celles disponibles. Une meilleure alternative doit être atteignable à partir de l'exécution incomplète avec un nombre minimal de compensations visibles (vis-à-vis le client). Pour une exécution alternative donnée, nous prouvons que le problème de décision associé au calcul du nombre de transitions invisiblement compensées est NP-Complet. De ce fait, nous concluons que le problème de décision associé au recouvrement appartient à la classe ΣP2.
25
Nijjar, Paul. "An Attempt to Automate NP-Hardness Reductions via SO∃ Logic." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1162.
Full textAbstract:
We explore the possibility of automating NP-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (SO∃) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms SO∃ sentences in a way that preserves NP-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two SO∃ sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary SO∃ sentence represents an NP-complete problem is undecidable.
26
Tourniaire, Emeric. "Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00874599.
Full textAbstract:
Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.
27
Ta, Thanh Thuy Tien. "New single machine scheduling problems with deadline for the characterization of optimal solutions." Thesis, Tours, 2018. http://www.theses.fr/2018TOUR4015/document.
Full textAbstract:
Nous considérons un problème d'ordonnancement à une machine avec dates de fin impératives et nous cherchons caractériser l'ensemble des solutions optimales, sans les énumérer. Nous supposons que les travaux sont numérotés selon la règle EDD et que cette séquence est réalisable. La méthode consiste à utiliser le treillis des permutations et d'associer à la permutation maximale du treillis la séquence EDD. Afin de caractériser beaucoup de solutions, nous cherchons une séquence réalisable aussi loin que possible de cette séquence. La distance utilisée est le niveau de la séquence dans le treillis, qui doit être minimum (le plus bas possible). Cette nouvelle fonction objectif est étudiée. Quelques cas particuliers polynomiaux sont identifiés, mais la complexité du problème général reste ouverte. Quelques méthodes de résolution, polynomiales et exponentielles, sont proposées et évaluées. Le niveau de la séquence étant en rapport avec la position des travaux dans la séquence, de nouvelles fonctions objectifs en rapport avec les positions des travaux sont identifiées et étudiées. Le problème de la minimisation de la somme pondérée des positions des travaux est prouvé fortement NP-difficile. Quelques cas particuliers sont étudiés et des méthodes de résolution proposées et évaluéesWe consider a single machine scheduling problem with deadlines and we want to characterise the set of optimal solutions, without enumerating them. We assume that jobs are numbered in EDD order and that this sequence is feasible. The key idea is to use the lattice of permutations and to associate to the supremum permutation the EDD sequence. In order to characterize a lot of solutions, we search for a feasible sequence, as far as possible to the supremum. The distance is the level of the sequence in the lattice, which has to be minimum. This new objective function is investigated. Some polynomially particular cases are identified, but the complexity of the general case problem remains open. Some resolution methods, polynomial and exponential, are proposed and evaluated. The level of the sequence being related to the positions of jobs in the sequence, new objective functions related to the jobs positions are identified and studied. The problem of minimizing the total weighted positions of jobs is proved to be strongly NP-hard. Some particular cases are investigated, resolution methods are also proposed and evaluated
28
Rocha, Thiago Alves. "Complexidade Descritiva de Classes de Complexidade ProbabilÃsticas de Tempo Polinomial e das Classes ⊕P e NP∩coNP AtravÃs de LÃgicas com Quantificadores de Segunda Ordem." Universidade Federal do CearÃ, 2014. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=12684.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel SuperiorVÃrios problemas computÃveis podem ser resolvidos de maneira mais eficiente ou mais natural atravÃs de algoritmos probabilÃsticos, o que mostra que o uso de tais algoritmos à bastante relevante em computaÃÃo. Entretanto, os algoritmos probabilÃsticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilÃsticos nÃo resolve problemas nÃo computÃveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaÃo e tempo, para resolvÃ-lo. Problemas que tem a mesma complexidade compÃem uma classe. As classes de complexidade computacional sÃo relacionadas atravÃs de uma hierarquia. A Complexidade Descritiva usa lÃgicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema nÃo depende de fatores fÃsicos, como tempo e espaÃo, mas apenas da expressividade da lÃgica que o define. Resultados importantes da Ãrea mostraram que vÃrias classes de complexidade computacional podem ser caracterizadas por lÃgicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da LÃgica de Segunda Ordem. Este estreito relacionamento entre tais Ãreas permite que alguns resultados da Ãrea de LÃgica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importÃncia de algoritmos probabilÃsticos e da Complexidade Descritiva, existem poucos resultados de caracterizaÃÃo, por lÃgicas, das classes de complexidade computacional probabilÃsticas. Neste trabalho, buscamos mostrar caracterizaÃÃes para cada uma das classes de complexidade probabilÃsticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitaÃÃo das mÃquinas nÃo-determinÃsticas dessas classes. Achamos caracterizaÃÃes lÃgicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lÃgica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterizaÃÃo de PP. Com essa mesma metodologia, tambÃm conseguimos caracterizar a classe ⊕P atravÃs de uma lÃgica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lÃgica com semÃntica probabilÃstica. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterizaÃÃo alternativa para essa classe. Com o mesmo mÃtodo, conseguimos caracterizar as classes probabilÃsticas semÃnticas RP, coRP, ZPP e a classe semÃntica NP∩coNP. Por fim, mostramos uma aplicaÃÃo dos resultados de Complexidade Descritiva na criaÃÃo de algoritmos atravÃs de uma especificaÃÃo lÃgica.
Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class ⊕P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP ∩ coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification.
29
Rocha, Thiago Alves. "Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem." reponame:Repositório Institucional da UFC, 2014. http://www.repositorio.ufc.br/handle/riufc/10588.
Full textAbstract:
ROCHA, T. A. Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem. 2014. 81 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014.Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:35:59Z No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5)
Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-02-09T15:45:32Z (GMT) No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5)
Made available in DSpace on 2015-02-09T15:45:32Z (GMT). No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) Previous issue date: 2014
Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class ⊕P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP ∩ coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification.
Vários problemas computáveis podem ser resolvidos de maneira mais eficiente ou mais natural através de algoritmos probabilísticos, o que mostra que o uso de tais algoritmos é bastante relevante em computação. Entretanto, os algoritmos probabilísticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilísticos não resolve problemas não computáveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaço e tempo, para resolvê-lo. Problemas que tem a mesma complexidade compõem uma classe. As classes de complexidade computacional são relacionadas através de uma hierarquia. A Complexidade Descritiva usa lógicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema não depende de fatores físicos, como tempo e espaço, mas apenas da expressividade da lógica que o define. Resultados importantes da área mostraram que várias classes de complexidade computacional podem ser caracterizadas por lógicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da Lógica de Segunda Ordem. Este estreito relacionamento entre tais áreas permite que alguns resultados da área de Lógica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importância de algoritmos probabilísticos e da Complexidade Descritiva, existem poucos resultados de caracterização, por lógicas, das classes de complexidade computacional probabilísticas. Neste trabalho, buscamos mostrar caracterizações para cada uma das classes de complexidade probabilísticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitação das máquinas não-determinísticas dessas classes. Achamos caracterizações lógicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lógica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterização de PP. Com essa mesma metodologia, também conseguimos caracterizar a classe ⊕P através de uma lógica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lógica com semântica probabilística. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterização alternativa para essa classe. Com o mesmo método, conseguimos caracterizar as classes probabilísticas semânticas RP, coRP, ZPP e a classe semântica NP∩coNP. Por fim, mostramos uma aplicação dos resultados de Complexidade Descritiva na criação de algoritmos através de uma especificação lógica.
30
Mohamed, Babou Hafedh. "Comparaison de réseaux biologiques." Phd thesis, Université de Nantes, 2012. http://tel.archives-ouvertes.fr/tel-00767578.
Full textAbstract:
La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans cette thèse, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le cas où D est cyclique, nous introduisons une méthode motivée par des hypothèses biologiques et consistant à décomposer D en DAGs tels que les sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous étudions également dans cette thèse, l'inférence des voies de signalisation en combinant les informations sur les causes et sur les effets des événements extra-cellulaires. Nous modélisons ce problème par un problème d'orientation de graphes mixtes et nous effectuons une étude de complexité permettant d'identifier les instances faciles et celles difficiles.
31
Kapfunde, Goodwell. "Near-capacity sphere decoder based detection schemes for MIMO wireless communication systems." Thesis, University of Hertfordshire, 2013. http://hdl.handle.net/2299/11350.
Full textAbstract:
The search for the closest lattice point arises in many communication problems, and is known to be NP-hard. The Maximum Likelihood (ML) Detector is the optimal detector which yields an optimal solution to this problem, but at the expense of high computational complexity. Existing near-optimal methods used to solve the problem are based on the Sphere Decoder (SD), which searches for lattice points confined in a hyper-sphere around the received point. The SD has emerged as a powerful means of finding the solution to the ML detection problem for MIMO systems. However the bottleneck lies in the determination of the initial radius. This thesis is concerned with the detection of transmitted wireless signals in Multiple-Input Multiple-Output (MIMO) digital communication systems as efficiently and effectively as possible. The main objective of this thesis is to design efficient ML detection algorithms for MIMO systems based on the depth-first search (DFS) algorithms whilst taking into account complexity and bit error rate performance requirements for advanced digital communication systems. The increased capacity and improved link reliability of MIMO systems without sacrificing bandwidth efficiency and transmit power will serve as the key motivation behind the study of MIMO detection schemes. The fundamental principles behind MIMO systems are explored in Chapter 2. A generic framework for linear and non-linear tree search based detection schemes is then presented Chapter 3. This paves way for different methods of improving the achievable performance-complexity trade-off for all SD-based detection algorithms. The suboptimal detection schemes, in particular the Minimum Mean Squared Error-Successive Interference Cancellation (MMSE-SIC), will also serve as pre-processing as well as comparison techniques whilst channel capacity approaching Low Density Parity Check (LDPC) codes will be employed to evaluate the performance of the proposed SD. Numerical and simulation results show that non-linear detection schemes yield better performance compared to linear detection schemes, however, at the expense of a slight increase in complexity. The first contribution in this thesis is the design of a near ML-achieving SD algorithm for MIMO digital communication systems that reduces the number of search operations within the sphere-constrained search space at reduced detection complexity in Chapter 4. In this design, the distance between the ML estimate and the received signal is used to control the lower and upper bound radii of the proposed SD to prevent NP-complete problems. The detection method is based on the DFS algorithm and the Successive Interference Cancellation (SIC). The SIC ensures that the effects of dominant signals are effectively removed. Simulation results presented in this thesis show that by employing pre-processing detection schemes, the complexity of the proposed SD can be significantly reduced, though at marginal performance penalty. The second contribution is the determination of the initial sphere radius in Chapter 5. The new initial radius proposed in this thesis is based on the variable parameter α which is commonly based on experience and is chosen to ensure that at least a lattice point exists inside the sphere with high probability. Using the variable parameter α, a new noise covariance matrix which incorporates the number of transmit antennas, the energy of the transmitted symbols and the channel matrix is defined. The new covariance matrix is then incorporated into the EMMSE model to generate an improved EMMSE estimate. The EMMSE radius is finally found by computing the distance between the sphere centre and the improved EMMSE estimate. This distance can be fine-tuned by varying the variable parameter α. The beauty of the proposed method is that it reduces the complexity of the preprocessing step of the EMMSE to that of the Zero-Forcing (ZF) detector without significant performance degradation of the SD, particularly at low Signal-to-Noise Ratios (SNR). More specifically, it will be shown through simulation results that using the EMMSE preprocessing step will substantially improve performance whenever the complexity of the tree search is fixed or upper bounded. The final contribution is the design of the LRAD-MMSE-SIC based SD detection scheme which introduces a trade-off between performance and increased computational complexity in Chapter 6. The Lenstra-Lenstra-Lovasz (LLL) algorithm will be utilised to orthogonalise the channel matrix H to a new near orthogonal channel matrix H ̅.The increased computational complexity introduced by the LLL algorithm will be significantly decreased by employing sorted QR decomposition of the transformed channel H ̅ into a unitary matrix and an upper triangular matrix which retains the property of the channel matrix. The SIC algorithm will ensure that the interference due to dominant signals will be minimised while the LDPC will effectively stop the propagation of errors within the entire system. Through simulations, it will be demonstrated that the proposed detector still approaches the ML performance while requiring much lower complexity compared to the conventional SD.
32
Lyaudet, Laurent. "Graphes et hypergraphes : complexités algorithmique et algébrique." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00905137.
Full textAbstract:
Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.
33
Kopřiva, Jan. "Srovnání algoritmů při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2009. http://www.nusl.cz/ntk/nusl-222126.
Full textAbstract:
The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).
34
Travers, Stephen. "Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes." Doctoral thesis, 2007. https://nbn-resolving.org/urn:nbn:de:bvb:20-opus-27124.
Full textAbstract:
This thesis is devoted to the study of computational complexity theory, a branch of theoretical computer science. Computational complexity theory investigates the inherent difficulty in designing efficient algorithms for computational problems. By doing so, it analyses the scalability of computational problems and algorithms and places practical limits on what computers can actually accomplish. Computational problems are categorised into complexity classes. Among the most important complexity classes are the class NP and the subclass of NP-complete problems, which comprises many important optimisation problems in the field of operations research. Moreover, with the P-NP-problem, the class NP represents the most important unsolved question in computer science. The first part of this thesis is devoted to the study of NP-complete-, and more generally, NP-hard problems. It aims at improving our understanding of this important complexity class by systematically studying how altering NP-hard sets affects their NP-hardness. This research is related to longstanding open questions concerning the complexity of unions of disjoint NP-complete sets, and the existence of sparse NP-hard sets. The second part of the thesis is also dedicated to complexity classes but takes a different perspective: In a sense, after investigating the interior of complexity classes in the first part, the focus shifts to the description of complexity classes and thereby to the exterior in the second part. It deals with the description of complexity classes through leaf languages, a uniform framework which allows us to characterise a great variety of important complexity classes. The known concepts are complemented by a new leaf-language model. To a certain extent, this new approach combines the advantages of the known models. The presented results give evidence that the connection between the theory of formal languages and computational complexity theory might be closer than formerly knownDiese Dissertation behandelt die Komplexitätstheorie, ein zentrales Teilgebiet der Theoretischen Informatik. Die Komplexitätstheorie untersucht die inhärente Schwierigkeit, effiziente Algorithmen für Berechnungsprobleme zu entwerfen. Sie analysiert die Skalierbarkeit von Berechnungsproblemen und Algorithmen und stellt grundsätzliche Grenzen für die Leistungsfähigkeit von Computern auf. Berechnungsprobleme werden in Komplexitätsklassen kategorisiert. Dabei spielen die Klasse NP und die in ihr enthaltene Klasse der NP-vollständigen Probleme eine wichtige Rolle. Letztere umfasst zahlreiche in der Praxis bedeutsame Probleme aus dem Bereich Operations Research. Darüber hinaus repräsentiert die Klasse NP mit dem P-NP Problem gleichfalls das wichtigste ungelöste Problem in der Informatik. Der erste Teil dieser Dissertation ist der Untersuchung NP-vollständiger und noch allgemeiner, NP-harter Mengen gewidmet. Durch eine systematische Untersuchung der Frage, wie sich partielle Modifikationen von Mengen auf deren NP-Härte auswirken, soll das Verständnis dieser wichtigen Komplexitätsklasse verbessert werden. Die Untersuchungen in diesem Bereich stehen in enger Verbindung zu wichtigen ungelösten Fragen, wie beispielsweise der Frage nach der Komplexität von Vereinigungen disjunkter NP-vollständiger Mengen und darüber hinaus der Frage nach der Existenz dünner, NP-harter Mengen. Der zweite Teil der Dissertation beschäftigt sich ebenfalls mit der Komplexitätstheorie, nimmt dabei aber eine andere Perspektive ein: Während im ersten Teil mit der Untersuchung struktureller Eigenschaften innere Aspekte von Komplexitätsklassen im Vordergrund stehen dreht es sich im zweiten Teil um die Beschreibung von Komplexitätsklassen. Dabei werden so genannte Blattsprachen verwendet, welche einen uniformen Beschreibungsmechanismus für Komplexitätsklassen darstellen. Die bestehenden Blattsprachen-Konzepte werden durch einen neuen Ansatz ergänzt, der in einem gewissen Sinne die Vorteile der bekannten Ansätze vereint. Die erzielten Ergebnisse sind Evidenz dafür, dass die Verbindung zwischen der Theorie der formalen Sprachen und der Komplexitätstheorie noch enger ist als bislang vermutet
35
"Complexity analysis of task assignment problems and vehicle scheduling problems." Chinese University of Hong Kong, 1994. http://library.cuhk.edu.hk/record=b5887281.
Full textAbstract:
by Chi-lok Chan.Thesis (M.Phil.)--Chinese University of Hong Kong, 1994.
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Scheduling Problems of Chain-like Task System --- p.4
Chapter 2.1 --- Introduction --- p.4
Chapter 2.2 --- Problem Assumptions and Notations Definition --- p.7
Chapter 2.3 --- Related Works --- p.9
Chapter 2.3.1 --- Bokhari's Algorithm --- p.10
Chapter 2.3.2 --- Sheu and Chiang's Algorithm --- p.12
Chapter 2.3.3 --- Hsu's Algorithm --- p.12
Chapter 2.4 --- Decision Algorithms for Un-mergeable Task System --- p.18
Chapter 2.4.1 --- Feasible Length-K Schedule --- p.18
Chapter 2.4.2 --- Generalized Decision Test --- p.23
Chapter 2.5 --- Dominated and Non-dominated Task Systems --- p.26
Chapter 2.5.1 --- Algorithm for Dominated Task System --- p.26
Chapter 2.5.2 --- Property of Non-dominated Task System --- p.27
Chapter 2.6 --- A Searching-Based Algorithm for the Optimization Problem --- p.28
Chapter 2.6.1 --- Algorithm --- p.29
Chapter 2.6.2 --- Complexity Analysis --- p.31
Chapter 2.7 --- A Searching Algorithm Based on a Sorted Matrix --- p.33
Chapter 2.7.1 --- Sorted Matrix --- p.33
Chapter 2.7.2 --- Algorithm for the Optimization Problem --- p.35
Chapter 2.7.3 --- Complexity Analysis --- p.40
Chapter 2.8 --- A Constructive Algorithm for the Optimization Problem --- p.43
Chapter 2.9 --- A Modified Constructive Algorithm --- p.46
Chapter 2.9.1 --- Algorithm --- p.46
Chapter 2.9.2 --- Worst-Case Analysis --- p.50
Chapter 2.9.3 --- Sufficient Condition for Efficient Algorithm H --- p.58
Chapter 2.9.4 --- Average-Case Analysis --- p.62
Chapter 2.10 --- Performance Evaluation --- p.65
Chapter 2.10.1 --- Optimal Schedule --- p.65
Chapter 2.10.2 --- Space Complexity Analysis --- p.67
Chapter 2.10.3 --- Time Complexity Analysis --- p.68
Chapter 2.10.4 --- Simulation of Algorithm F and Algorithm H --- p.70
Chapter 2.11 --- Conclusion --- p.74
Chapter 3 --- Vehicle Scheduling Problems with Time Window Constraints --- p.77
Chapter 3.1 --- Introduction --- p.77
Chapter 3.2 --- Problem Formulation and Notations --- p.79
Chapter 3.3 --- NP-hardness of VSP-WINDOW-SLP --- p.83
Chapter 3.3.1 --- A Transformation from PARTITION --- p.83
Chapter 3.3.2 --- Intuitive Idea of the Reduction --- p.85
Chapter 3.3.3 --- NP-completeness Proof --- p.87
Chapter 3.4 --- Polynomial Time Algorithm for the VSP-WINDOW on a Straight Line with Common Ready Time --- p.98
Chapter 3.5 --- Strong NP-hardness of VSP-WINDOW-TREEP --- p.106
Chapter 3.5.1 --- A Transformation from 3-PARTITION --- p.107
Chapter 3.5.2 --- NP-completeness Proof --- p.107
Chapter 3.6 --- Conclusion --- p.111
Chapter 4 --- Conclusion --- p.115
Bibliography --- p.119
36
Travers, Stephen [Verfasser]. "Structural properties of NP-hard sets and uniform characterisations of complexity classes / vorgelegt von Stephen Travers." 2008. http://d-nb.info/988512785/34.
Full text
37
Churchley, Ross William. "On graph-transverse matching problems." Thesis, 2012. http://hdl.handle.net/1828/4137.
Full textAbstract:
Given graphs G,H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently.
The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.Graduate
38
Sauer, Paul Van der Merwe. "The complexity of unavoidable word patterns." Thesis, 2019. http://hdl.handle.net/10500/27343.
Full textAbstract:
Bibliography: pages 192-195The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established.
Decision Sciences
D. Phil. (Operations Research)
39
Mousavi, Nima. "Algorithmic Problems in Access Control." Thesis, 2014. http://hdl.handle.net/10012/8303.
Full textAbstract:
Access control is used to provide regulated access
to resources by principals. It is an important and foundational
aspect of information security. Role-Based Access Control (RBAC) is
a popular and widely-used access control model,
that, as prior work argues,
is ideally suited for enterprise settings. In this dissertation,
we address two problems in the context of RBAC.
One is the User Authorization Query (UAQ) problem, which relates
to sessions that a user creates to exercise permissions.
UAQ's objective is the identification of a
set of roles that a user needs to activate such that the session is
authorized to all permissions that the user wants to exercise in
that session. The roles that are activated must respect
a set of Separation of Duty constraints. Such constraints restrict the
roles that can be activated together in a session.
UAQ is known to be intractable (NP-hard).
In this dissertation, we give a precise formulation of UAQ as a
joint-optimization problem, and analyze it.
We examine the manner in which each input parameter contributes to its
intractability.
We then propose an approach to mitigate its intractability based on
our observation that a corresponding decision version of the problem
is in NP. We efficiently
reduce UAQ to Boolean satisfiability in conjunctive normal form
(CNF-SAT), a well-known
NP-complete problem for which solvers exist that are efficient for large
classes of instances. We also present results for UAQ posed
as an approximation problem; our results
suggest that efficient approximation is not promising for UAQ.
We discuss an open-source implementation of our approach and a
corresponding empirical assessment that we have conducted.
The other problem we consider in this dissertation regards
an efficient data structure for distributed
access enforcement. Access enforcement is the process of validating an access
request to a resource.
Distributed access enforcement has become important
with the proliferation of data, which requires access control systems
to scale to tens of thousands of resources and permissions.
Prior work has shown the effectiveness of a data structure called
the Cascade Bloom Filter (CBF) for this problem.
In this dissertation, we study the construction of instances
of the CBF.
We formulate the problem of finding an optimal instance of a
CBF, where optimality refers to the number of false positives
incurred and the number
of hash functions used. We prove that this problem
is NP-hard, and a meaningful decision version is in NP.
We then propose an approach to mitigate the intractability of
the problem by reducing it to
CNF-SAT, that allows us to use a SAT solver for instances that
arise in practice.
We discuss an open-source implementation of our approach
and an empirical assessment based on it.
40
Made, Vollenweider Ignacio. "De PH a IP : un curso en complejidad computacional." Bachelor's thesis, 2019. http://hdl.handle.net/11086/16009.
Full textAbstract:
Tesis (Lic. en Cs. de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2019.En este trabajo estudiamos algunas de las clases más importantes de la teoría de Complejidad Computacional. Nos basamos en el programa que propone el libro Computational Complexity a modern approach, del cual vemos la segunda mitad de la primera parte del programa (excluyendo Criptografía, Computación Cuántica y el Teorema PCP). En particular, estudiamos la clase de la Jerarquía Polinomial (PH), la clase de Circuitos Booleanos (P /poly ), la Computación Randomizada (BPP) y los Protocolos Interactivos (IP). Además vemos las principales técnicas de la teoría para obtener resultados las cuales son Diagonalización, Lower bounds y Arithmetization. Y estudiamos también sus respectivas limitaciones: Relativización, Natural proofs y Algebrization.
In this work we study some of the most important classes of the Computational Complexity Theory. We base on the program proposed by the book Computational Complexity a modern approach, of which we see the second half of the first part of the program (excluding Cryptography, Quantum Computing and the PCP Theorem). In particular, we study the class of the Polynomial Hierarchy (PH), the class of Boolean Circuits (P /poly ), the Randomized Computing (BPP) and the Interactive Protocols (IP). In addition we see the main techniques of the theory to obtain results which are Diagonalization, Lower bounds and Arithmetization. And we also study their respective limitations: Relativization, Natural proofs and Algebrization.
Fil: Made Vollenweider, Ignacio. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina.
41
Jirotka, Tomáš. "NP vyhledávací problémy." Master's thesis, 2011. http://www.nusl.cz/ntk/nusl-300252.
Full textAbstract:
Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1
42
Kosub, Sven. "Complexity and Partitions." Doctoral thesis, 2001. https://nbn-resolving.org/urn:nbn:de:bvb:20-opus-2808.
Full textAbstract:
Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of classification problems for relations. For instance, a binary relation R typically defines a partitioning of the set of all pairs (x,y) into four parts, classifiable according to the cases where R(x,y) and R(y,x) hold, only R(x,y) or only R(y,x) holds or even neither R(x,y) nor R(y,x) is true. By means of concrete classification problems such as Graph Embedding or Entailment (for propositional logic), this thesis systematically develops tools, in shape of the boolean hierarchy of NP-partitions and its refinements, for the qualitative analysis of the complexity of partitions generated by NP-relations. The Boolean hierarchy of NP-partitions is introduced as a generalization of the well-known and well-studied Boolean hierarchy (of sets) over NP. Whereas the latter hierarchy has a very simple structure, the situation is much more complicated for the case of partitions into at least three parts. To get an idea of this hierarchy, alternative descriptions of the partition classes are given in terms of finite, labeled lattices. Based on these characterizations the Embedding Conjecture is established providing the complete information on the structure of the hierarchy. This conjecture is supported by several results. A natural extension of the Boolean hierarchy of NP-partitions emerges from the lattice-characterization of its classes by considering partition classes generated by finite, labeled posets. It turns out that all significant ideas translate from the case of lattices. The induced refined Boolean hierarchy of NP-partitions enables us more accuratly capturing the complexity of certain relations (such as Graph Embedding) and a description of projectively closed partition classesDie klassische Komplexitätstheorie untersucht in erster Linie die Komplexität von Mengen, d.h. von Zerlegungen (Partitionen) einer Grundmenge in zwei Teile. Häufig werden aber natürliche Fragestellungen viel angemessener durch Zerlegungen in mehr als zwei Teile abgebildet. Eine besonders interessante Klasse solcher Fragestellungen sind Klassifikationsprobleme für Relationen. Zum Beispiel definiert eine Binärrelation R typischerweise eine Zerlegung der Menge aller Paare (x,y) in vier Teile, klassifizierbar danach, ob R(x,y) und R(y,x), R(x,y) aber nicht R(y,x), nicht R(x,y) aber dafür R(y,x) oder weder R(x,y) noch R(y,x) gilt. Anhand konkreter Klassifikationsprobleme, wie zum Beispiel der Einbettbarkeit von Graphen und der Folgerbarkeit für aussagenlogische Formeln, werden in der Dissertation Instrumente für eine qualitative Analyse der Komplexität von Partitionen, die von NP-Relationen erzeugt werden, in Form der Booleschen Hierarchie der NP-Partitionen und ihrer Erweiterungen systematisch entwickelt. Die Boolesche Hierarchie der NP-Partitionen wird als Verallgemeinerung der bereits bekannten und wohluntersuchten Boolesche Hierarchie über NP eingeführt. Während die letztere Hierarchie eine sehr einfache Struktur aufweist, stellt sich die Boolesche Hierarchie der NP-Partitionen im Falle von Zerlegungen in mindestens 3 Teile als sehr viel komplizierter heraus. Um einen Überblick über diese Hierarchien zu erlangen, werden alternative Beschreibungen der Klassen der Hierarchien mittels endlicher, bewerteter Verbände angegeben. Darauf aufbauend wird die Einbettungsvermutung aufgestellt, die uns die vollständige Information über die Struktur der Hierarchie liefert. Diese Vermutung wird mit verschiedene Resultaten untermauert. Eine Erweiterung der Booleschen Hierarchie der NP-Partitionen ergibt sich auf natürliche Weise aus der Charakterisierung ihrer Klassen durch Verbände. Dazu werden Klassen betrachtet, die von endlichen, bewerteten Halbordnungen erzeugt werden. Es zeigt sich, dass die wesentlichen Konzepte vom Verbandsfall übertragen werden können. Die entstehende Verfeinerung der Booleschen Hierarchie der NP-Partitionen ermöglicht die exaktere Analyse der Komplexität bestimmter Relationen (wie zum Beispiel der Einbettbarkeit von Graphen) und die Beschreibung projektiv abgeschlossener Partitionenklassen
43
Ristad, Eric Sven. "GPSG-Recognition is NP-Hard." 1985. http://hdl.handle.net/1721.1/5615.
Full textAbstract:
Proponents of generalized phrase structure grammar (GPSG) cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. Since context-free languages (CFLs) can be parsed in time proportional to the cube of the sentence length, and GPSGs only generate CFLs, it seems plausible the GPSGs can also be parsed in cubic time. This longstanding, widely assumed GPSG "efficient parsability" result in misleading: parsing the sentences of an arbitrary GPSG is likely to be intractable, because a reduction from 3SAT proves that the universal recognition problem for the GPSGs of Gazdar (1981) is NP-hard. Crucially, the time to parse a sentence of a CFL can be the product of sentence length cubed and context-free grammar size squared, and the GPSG grammar can result in an exponentially large set of derived context-free rules. A central object in the 1981 GPSG theory, the metarule, inherently results in an intractable parsing problem, even when severely constrained. The implications for linguistics and natural language parsing are discussed.
44
Wulff, Sharon Jay. "Computational Complexity Of Bi-clustering." Thesis, 2008. http://hdl.handle.net/10012/3900.
Full textAbstract:
In this work we formalize a new natural objective (or cost) function
for bi-clustering - Monochromatic bi-clustering. Our objective function is
suitable for detecting meaningful homogenous clusters based on
categorical valued input matrices. Such problems have arisen recently in
systems biology where researchers have inferred functional classifications
of biological agents based on their pairwise interactions. We
analyze the computational complexity of the resulting optimization
problems. We show that finding optimal solutions is NP-hard and
complement this result by introducing a polynomial time
approximation algorithm for this bi-clustering task. This is the first positive
approximation guarantee for bi-clustering algorithms. We also show
that bi-clustering with our objective function can be viewed as a
generalization of correlation clustering.
45
Chester, Sean. "Representative Subsets for Preference Queries." Thesis, 2013. http://hdl.handle.net/1828/4833.
Full textAbstract:
We focus on the two overlapping areas of preference queries and dataset summarization. A (linear) preference query specifies the relative importance of the attributes in a dataset and asks for the tuples that best match those preferences. Dataset summarization is the task of representing an entire dataset by a small, representative subset. Within these areas, we focus on three important sub-problems, significantly advancing the state-of-the-art in each.
We begin with an investigation into a new formulation of preference queries, identifying a neglected and important subclass that we call threshold projection queries. While literature typically constrains the attribute preferences (which are real-valued weights) such that their sum is one, we show that this introduces bias when querying by threshold rather than cardinality. Using projection, rather than inner product as in that literature, removes the bias. We then give algorithms for building and querying indices for this class of query, based, in the general case, on geometric duality and halfspace range searching, and, in an important special case, on stereographic projection.
In the second part of the dissertation, we investigate the monochromatic reverse top-k
(mRTOP) query in two dimensions. A mRTOP query asks for, given a tuple and a dataset,
the linear preference queries on the dataset that will include the given tuple. Towards this goal, we consider the novel scenario of building an index to support mRTOP queries, using geometric duality and plane sweep. We show theoretically and empirically that the index is quick to build, small on disk, and very efficient at answering mRTOP queries. As a corollary to these efforts, we defined the top-k rank contour, which encodes the k-ranked tuple for every possible linear preference query. This is tremendously useful in answering mRTOP queries, but also, we posit, of significant independent interest for its relation to myriad related linear preference query problems. Intuitively, the top-k rank contour is the minimum possible representation of knowledge needed to identify the k-ranked tuple for any query, without apriori knowledge of that query.
We also introduce k-regret minimizing sets, a very succinct approximation of a numeric
dataset. The purpose of the approximation is to represent the entire dataset by just a small subset that nonetheless will contain a tuple within or near to the top-k for any linear preference query. We show that the problem of finding k-regret minimizing sets—and, indeed, the problem in literature that it generalizes—is NP-Hard. Still, for the special case of two dimensions, we provide a fast, exact algorithm based on the top-k rank contour. For arbitrary dimension, we introduce a novel greedy algorithm based on linear programming and randomization that does excellently in our empirical investigation.Graduate
0984