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 14 of 14 for “"Iterative rounding"”.

  1. Iterative Rounding Approximation Algorithms in Network Design

    Iterative rounding has been an increasingly popular approach to solving network design optimization problems ever since Jain introduced the concept in his revolutionary 2-approximation for the Survivable Network Design Problem (SNDP). This paper looks at several important iterative rounding …

    waterloo Repository record for Iterative Rounding Approximation Algorithms in Network Design (opens in a new tab)

  2. Covering points with axis parallel lines

    … number of axis parallel lines. We use the iterative rounding approach which gives an integral solution to the problem. We also propose a combinatorial algorithm by using the branch and bound technique which gives an optimal integral solution to the point cover problem. Later we implemented …

    lethbridge Repository record for Covering points with axis parallel lines (opens in a new tab)

  3. Algorithms for multi-trip vehicle routing and device to device communications

    … for the minimization objective. We give an iterative rounding algorithm that achieves at least a quarter of the optimal sum rate and no more than the required maximum of the total interference when the objective is to maximize sum-rate. Detailed experiments are performed on synthetic as well …

    lethbridge Repository record for Algorithms for multi-trip vehicle routing and device to device communications (opens in a new tab)

  4. Approximation Algorithms for Relative Survivable Network Design Problems

    … algorithm for SND exists, using the method of iterative rounding. In 2022, Dinitz et al. introduced a problem that we refer to as Path-Relative Survivable Network Design (PRSND), a natural extension of SND that addresses cases where the underlying graph does not have the required connectivity; …

    waterloo Repository record for Approximation Algorithms for Relative Survivable Network Design Problems (opens in a new tab)

  5. Energy-Efficient Workload Placement with Bounded Slowdown in Disaggregated Datacenters

    … develop a workload placement algorithm, called Iterative Rounding-based Placement ( IRoP), that given a set of workloads, determines where to place each workload (i.e., on which CPU) and how much local and remote memory is allocated to it. The key insight in designing IRoP is that the impact of …

    calgary Repository record for Energy-Efficient Workload Placement with Bounded Slowdown in Disaggregated Datacenters (opens in a new tab)

  6. Prize-Collecting Network Design

    … the prizecollecting Steiner forest problem using iterative rounding. In the second setting, we give an O(log n)-competitive algorithm for the constrained forest problem with 0-1 proper connectivity requirement functions using the primal-dual method and extend our algorithm to solve its …

    cornell Repository record for Prize-Collecting Network Design (opens in a new tab)

  7. Secure Minimum Time Data Collection (SMTDC) protocol for wireless sensor networks

    … and solve it using linear relaxation based iterative rounding (LR-IR). During the time scheduling phase of SMTDC, we use a heuristic time-slot arrangement algorithm to solve the tree scheduling problem. The proposed algorithms and schemes are validated through simulation experiments using …

    uiuc Repository record for Secure Minimum Time Data Collection (SMTDC) protocol for wireless sensor networks (opens in a new tab)

  8. Modeling Regulated Electricity Markets: Scalable Algorithms, Market Constraints, and Applications in Southeast Asia

    … problem attributes with two heuristics, Iterative Rounding and Column Generation. These heuristics are evaluated on country-scale power systems in terms of runtime, solution quality, and scalability. Building on the resulting modeling framework, this research then turns to the challenge …

    cornell Repository record for Modeling Regulated Electricity Markets: Scalable Algorithms, Market Constraints, and Applications in Southeast Asia (opens in a new tab) Embargoed until 2028-06-22

  9. Structure in Stable Matching Problems

    In this thesis we provide two contributions to the study of structure in stable matching problems. The first contribution is a short new proof for the integrality of Rothblum’s linear description of the convex hull of incidence vectors of stable matchings in bipartite graphs. The key feature of our …

    waterloo Repository record for Structure in Stable Matching Problems (opens in a new tab)

  10. Cover Small Cuts and Flexible Graph Connectivity Problems

    … used to prove the approximation ratio of Jain's iterative rounding approximation algorithm does not hold. We show that families of “small cuts” are always strongly pliable, but not all strongly pliable families can be realized as families of small cuts. We prove a 5-approximation algorithm for …

    waterloo Repository record for Cover Small Cuts and Flexible Graph Connectivity Problems (opens in a new tab)

  11. Dynamic Graph Generation and an Asynchronous Parallel Bundle Method Motivated by Train Timetabling

    … real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In …

    qucosa-diss

  12. Survivable network design problems with element and vertex connectivity requirements

    … work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate …

    uiuc Repository record for Survivable network design problems with element and vertex connectivity requirements (opens in a new tab)

  13. Fair and diverse data representation in machine learning

    The work contains two major lines of research: subset selection and multi-criteria dimensionality reduction with an application to fairness. Subset selection can be applied to a classical problem of optimal design in statistics and many others in machine learning when learning is subject to a …

    gatech Repository record for Fair and diverse data representation in machine learning (opens in a new tab)

  14. Bridging Discrete and Continuous Methods for Faster Optimization and Machine Learning

    … has not been adequately integrated within the iterative optimization framework, leaving a significant opportunity to speed-up continuous optimization algorithms used in machine and online learning. Although the theory of combinatorial and continuous optimization methods has evolved …

    gatech Repository record for Bridging Discrete and Continuous Methods for Faster Optimization and Machine Learning (opens in a new tab)