Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 44 for “"Polynomial algorithm"”.
-
On Vegh's Strongly Polynomial Algorithm for Generalized Flows
… contains an exposition of the new strongly polynomial algorithm for the generalized flow problem by Laszlo Vegh (2013). It has been a long-standing open question whether such an algorithm exists, until it was resolved by Vegh in 2013. Generalized flows have many applications in economic …
-
A Polynomial Algorithm for a NP-hard to solve Optimization Problem
… number of different asset classes, an efficient algorithm is developed for finding the exact solution in the case of specially distributed losses. Applying this algorithm to even more general loss distributions results in a not necessarily exact matching of the VaR optimum. However, in this case, …
-
Matchings with a size constraint
… and (g, f)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching problem, and a strongly polynomial algorithm which can find …
-
CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES
… partition under super stability condition admits polynomial algorithm.
-
On generalized movement scheduling problem
… the GMS problem is NP-complete. An optimal polynomial algorithm is developed for the GMS problem without node conflict. In the MPL problem, if the speed of object differs in different intervals, the problem is proved to be NP-complete. An optimal polynomial algorithm is developed to find the …
-
Matching theory: subgraphs with degree constraints and other properties
… number of inequalities can be reduced to a polynomial number of inequalities. The second problem is the general factor problem. Let G = (V, E) be a multigraph. An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex ʋ E Ʋ. We call a B-factor a spanning subgraph F of G …
-
Scheduling Of 2-Operation Jobs On A Single Machine To Minimize The Number Of Tardy Jobs
… computational time. Till date only a pseudo-polynomial algorithm is given to solve this problem with no concrete computational experiments designed to prove the efficiency and working of the algorithm for different problem instances. We propose a heuristic algorithm based on the …
-
Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών
… colinear and linear graphs. Moreover, we present polynomial-time algorithms or NP-completeness results for various types of the coloring problem on graphs and polynomial-time algorithms for the longest path problem on perfect graphs. In particular, motivated by the de nition of linear coloring on …
-
Scheduling jobs on two uniform parallel machines to minimize the makespan
… We propose several heuristic-based online algorithms for machines with different speeds called Q2||Cmax. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q2||Cmax using pseudo-polynomial algorithms based on dynamic programming method. The …
-
Bar-representable visibility graphs and a related network flow problem
… are the visibility graphs of some bar layout. A polynomial time algorithm for determining if a given graph is bar-representable, and the subsequent construction of an associated layout are provided. Weighted and directed versions of the problem are also formulated and solved; in particular, …
-
On the optimization problems in multiaccess communication systems
… problems known as NP-complete, and no polynomial algorithm can possibly solve them. Conventional methods may not be efficient arid often produce poor solutions. In this dissertation, we propose a neural network-based algorithm for solving NP-complete problems encountered in multi-access …
-
Planar Open Rectangle-of-Influence Drawings
… community in rectangle-of-influence drawings, no algorithm is known to test whether a graph has a planar open weak RI-drawing, not even for inner triangulated graphs. In this thesis, we have two major contributions. First we study open weak RI-drawings of plane graphs that must have a non-aligned …
-
New Directions in Multivariate Public Key Cryptography
… enough quantum computers can be built, Shor's algorithm will render them completely insecure. Multivariate public key cryptosystems (MPKC) are one possible alternative. MPKC makes use of the fact that solving multivariate polynomial systems over a finite field is an NP-complete problem, for …
-
Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)
… into two smaller problems. The result is a polynomial algorithm which finds a minimum-delay routing assignment by solving a series of static maximum-flow problems. In order to apply the above ideas to dynamic networks with continuously-varying capacities, a continuous network is defined …
-
Quadratic programming : quantitative analysis and polynomial running time algorithms
… quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial algorithm for solving linear programming problems in which the number of …
-
The Battery Charging Problem and Linear Programs with Random Coefficient Matrix
… shortest path problem and as result we propose a polynomial algorithm to solve the problem in the deterministic setting. Then we study the optimization of a battery under the uncertainty of charge and discharge prices. We compare the performance of various policy generation methods in Markovian or …
-
Adding a new dimension to the upward drawing
… for the drawing. We propose an O( n * width(P)) algorithm which satisfies this new requirement. Furthermore, this new idea is studied for the subclass of N-free ordered sets. We present some techniques of improving the readability by locally reducing crossings around some component of the …
-
Estimation and optimization problems in revenue management with customer choice behavior
… parameters are identifiable. We then propose an algorithm to recover any non-homogeneous arrival rate. The estimation from the proposed algorithm theoretically converges to the true parameter. The numerical experiments also show that the algorithm has good practical performance. The second part …
-
High resolution modal analysis using poles obtained at a single location
… from the accelerometer FRF using the Rational Polynomial algorithm. Mode vectors were then estimated from the 472 SLV FRFs for the first 6 modes (1 rigid body + 5 flexible). A comparison of the results was given between the proposed method and a standard global parameter estimation technique. …
-
Algorithms and Complexity for Alliances and Weighted Alliances of Various Types
… recently, no research has been done to develop algorithms or establish the complexity of decision problems for alliances in graphs. This thesis presents the first algorithmic study of alliances in graphs. We present linear algorithms for finding various alliance numbers in trees and series …
Page 1 of 3