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 20 for “"set packing"”.

  1. Generalized Set and Graph Packing Problems

    … These graph problems generalize the classical H-Packing problem [88] in two different ways. In the H-Packing with t-Overlap problem, the goal is to find in a given graph G (the network) at least k subgraphs (the communities) isomorphic to a member of a family of graphs H (the community models) …

    waterloo Repository record for Generalized Set and Graph Packing Problems (opens in a new tab)

  2. A quadratic partial assignment and packing model and algorithm for the airline gate assignment problem

    … variant of the quadratic assignment problem with set packing constraints. The quadratic objective function is then transformed into an equivalent linearized form by applying the first-order linearization technique of Sherali and Adams [1989, 1990]. In addition to linearizing the problem, the …

    vt Repository record for A quadratic partial assignment and packing model and algorithm for the airline gate assignment problem (opens in a new tab)

  3. Algorithmic Fairness and Online Decision Making in Combinatorial Optimization and Unsupervised Learning

    … learning problems such as graph matching, set packing, and clustering are commonly used to model large-scale real-world applications. Examples of such applications include facility location problems to provide services in emergency, online advertising markets (matching ads to customers), …

    maryland Repository record for Algorithmic Fairness and Online Decision Making in Combinatorial Optimization and Unsupervised Learning (opens in a new tab)

  4. Weapon-target pairing revising an air tasking order in real-time

    … and (e) avoid the attrition of tasked assets. This thesis develops an automated, optimizing, heuristic decision aid, "RAPT-OR", that rapidly revises a current Air Taking Order (ATO) to meet the requirements above. Using a set-packing model, RAPT-OR, an ATO near optimally, on a desktop PC, …

    nps Repository record for Weapon-target pairing revising an air tasking order in real-time (opens in a new tab)

  5. The selection of counties and locations of field site coordinators.

    … program. This problem is defined as a multiple set packing problem (MSPP). Also, the locations of the FSCs need to be determined such that the total weighted distance is minimized. This problem is defined as the FSC location problem (FLP). Therefore, in this thesis, mathematical models are …

    wvu Repository record for The selection of counties and locations of field site coordinators. (opens in a new tab)

  6. Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics

    … novel classes of DOI for the general context of set cover problems. We refer to these as Smooth DOI (S-DOI) and Flexible DOI (F-DOI). S-DOI can be interpreted as allowing for the undercovering of items at the cost of overcovering others and incurring an objective penalty. SDOI leverage the fact …

    maryland Repository record for Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics (opens in a new tab)

  7. A new hierarchy of relaxations for 0-1 mixed integer problems with application to some specially structured problems

    … upper bounding (VUB), covering, partitioning and packing constraints, as well as sparsity, can be exploited within this framework. For some types of structures, low level relaxations are exhibited to recover the convex hull of integer feasible solutions. An alternative partial application of this …

    vt Repository record for A new hierarchy of relaxations for 0-1 mixed integer problems with application to some specially structured problems (opens in a new tab)

  8. Mathematical Programming-based Models and Methods for University Course Timetabling

    … practical problems which feature an arbitrary set of room types. For the room assignment problem, we define a set packing integer programme within a lexicographic optimisation process, to consider several quality measures. An analysis of the matrix structure for this model yields insights into …

    auckland-ms Repository record for Mathematical Programming-based Models and Methods for University Course Timetabling (opens in a new tab)

  9. The Computational Complexity of Some Games and Puzzles With Theoretical Applications

    … inapproximability results. Second, we study the SET game, a card game where the objective is to form sets of cards that match in a certain sense using cards from a special deck. We study single- and multi-round variations of this game and establish interesting con- nections with other classical …

    cuny-grad Repository record for The Computational Complexity of Some Games and Puzzles With Theoretical Applications (opens in a new tab)

  10. Parallel machine scheduling with time windows

    … addresses the problem of scheduling a set of jobs with multiple priorities on nonhomogeneous, parallel machines. The application of interest involves the tracking and data relay satellite system (TDRSS) run by the U.S. National Aeronautics and Space Administration. This system acts as a …

    texas Repository record for Parallel machine scheduling with time windows (opens in a new tab)

  11. Stochastic Integer Programming: Decomposition Methods and Industrial Applications

    … approach to solve a stochastic version of the set packing problem. The proposed method is quite effective in numerical experiments and outperforms the commercial solver dramatically in most cases. We study the sensitivity of different density of patterns and find our proposed method is more …

    toronto-retro Repository record for Stochastic Integer Programming: Decomposition Methods and Industrial Applications (opens in a new tab)

  12. Parameterized Approximation Results for Clustering and Graph Packing Problems

    The domains of clustering and graph packing have been the focus of extensive research across multiple disciplines, including optimization, machine learning, data mining, computational geometry, and operations research. Many central problems in these domains are known to be NP-hard, prompting the …

    aalto Repository record for Parameterized Approximation Results for Clustering and Graph Packing Problems (opens in a new tab)

  13. Representations and Parameterizations of Combinatorial Auctions

    … WDP for CAs, although it has been used to solve set packing, which is related to WDP for CAs and is discussed in detail. We investigate a few parameterizations of WDP; some of the parameterizations are shown to be fixed-parameter intractable, while others are fixed-parameter tractable. We also …

    waterloo Repository record for Representations and Parameterizations of Combinatorial Auctions (opens in a new tab)

  14. Dynamic Decision Support for Regional LTL Carriers

    … stages, each stage requiring the solution of a set packing models in which columns represent driver duties. Each stages determines admissible driver duties. The quality and efficiency of the solution approach are demonstrated through a computational study with real-life data from one of the …

    gatech Repository record for Dynamic Decision Support for Regional LTL Carriers (opens in a new tab)

  15. The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem

    … bounding (GUS) constrained knapsack problem, the set partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure …

    vt Repository record for The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem (opens in a new tab)

  16. Planning of mobile clinic operations

    … Pour résoudre le MLRP, une formulation de type set-packing qui repose sur la génération de routes a été mise en oeuvre. L’optimisation du modèle proposé permet de sélectionner les dépôts et les routes de véhicules qui seront exécutées à chaque période de l’horizon de planification, c’est-à-dire …

    uqam Download PDF for Planning of mobile clinic operations (opens in a new tab)

  17. Especificación y verificación de programas moleculares en PVS

    … problemas clásicos NP-completos: el problema Subset-Sum, el problema de la Mochila 0/1 acotado, el problema del empaquetamiento, Set Packing¸ el del recubrimiento exacto, Exact Cover, y el problema del recubrimiento minimal. A continuación se puede decir que empieza una segunda parte en la …

    sevilla Repository record for Especificación y verificación de programas moleculares en PVS (opens in a new tab)

  18. Routing and Scheduling with Time Windows: Models and Algorithms for Tramp Sea Cargos and Rail Car-Blocks

    … locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The …

    gatech Repository record for Routing and Scheduling with Time Windows: Models and Algorithms for Tramp Sea Cargos and Rail Car-Blocks (opens in a new tab)

  19. Hardness results and approximation algorithms for some problems on graphs

    … the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such …

    waterloo Repository record for Hardness results and approximation algorithms for some problems on graphs (opens in a new tab)