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 6 of 6 for “"Maximum Cut Problem"”.
-
A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming
… primal-dual approximation algorithms for NP-hard problems. The focus lies on the literature that followed the celebrated Goemans and Williamson approximation algorithm for the maximum cut problem, and thus on the use of semidefinite programming (SDP). We present a primal-dual conic optimization …
-
A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE
The Binary Quadratic Optimization Problem is a classical problem and studied in many fields. Typical applications include the 0-1 Quadratic Problem (QP), the Maximum Cut Problem (MAXCUT), k-Cluster Problem (kCluster), Maximum Independent Set Problem (MIS) as well as the Exact k-Quadratic Knapsack …
-
Analysis of Convex Relaxations for Nonconvex Optimization
… aspect of dealing with a nonconvex optimization problem is to study its convex relaxation, which is often part of some approximation algorithms that can find quality solutions to the original nonconvex problem. In this dissertation, we analyze two prominent ways of obtaining convex relaxations: …
-
Algorithms for Some Clustering Problems
… for the uncapacitated facility location problem: the primal-dual algorithm of Jain & Vazirani, and an algorithm of Mettu & Plaxton. The main result answers positively a question posed by Jain and Vazirani of whether their algorithm can be modified to attain a desired "continuity" …
-
New Convex Relaxations for the Maximum Cut and VLSI Layout Problems
It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NP-hard. Hence much research has been devoted to finding <I>good</I> relaxations for these hard problems. Usually a <I>good</I> relaxation is one which can be …