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 28 for “"FPTAS"”.

  1. An FPTAS for Total Weighted Earliness Tardiness Problem with Constant Number of Distinct Due Dates and Polynomially Related Weights

    … TWET problem first and then convert it into an FPTAS by adopting a rounding scheme.</p> <p>There are several important points in our algorithm: we observe the importance of the straddlers and guess them at the beginning through exhaustive enumeration, and insert them back at the very end by …

    mcmaster Repository record for An FPTAS for Total Weighted Earliness Tardiness Problem with Constant Number of Distinct Due Dates and Polynomially Related Weights (opens in a new tab)

  2. An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates

    … a Fully Polynomial Time Approximation Scheme (FPTAS) for the minimum total weighted tardiness (TWT) problem with a constant number ofdistinct due dates.</p> <p>Given a sequence ofjobs on a single machine, each with a weight, processing time, and a due date, the tardiness of a job is the amount …

    mcmaster Repository record for An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates (opens in a new tab)

  3. Improved approximation algorithms for packing and scheduling problems

    … and scheduling problems. First, improved AFPTAS for the Bin Packing Problem (BP) and its generalization, the Variable-sized Bin Packing Problem (VBP), are explained. Our algorithms have to solve the unbounded variant of the Knapsack Problem (KP) and of the Knapsack Problem with Inversely …

    cau-kiel Repository record for Improved approximation algorithms for packing and scheduling problems (opens in a new tab)

  4. In-depth site characterization of poly- and perfluoroalkyl substances at an abandoned fire protection training area, An

    … soil at several fire protection training areas (FPTAs) at concentrations well above provisional health advisory levels as a result of aqueous film forming foam application (AFFF). Many FPTAs have been remediated for fuel based contaminants that infiltrated the surface after years of training, but …

    colo-mines Repository record for In-depth site characterization of poly- and perfluoroalkyl substances at an abandoned fire protection training area, An (opens in a new tab)

  5. Investigations on two classes of covering problems

    … barrier coverage can be solved with an FPTAS. Along the way to developing the FPTAS, we give a fast, simple 2-approximation algorithm for weighted disjoint barrier coverage.

    lethbridge Repository record for Investigations on two classes of covering problems (opens in a new tab)

  6. EFFICIENT ALGORITHMS FOR GEOMETRIC OPTIMIZATION AND SYMMETRIC CONE PROGRAMMING

    … fully polynomial-time approximation schemes (FPTAS). Additionally, we propose two new approximation algorithms for SCPs, generalizing prior work on linear and semidefinite programming. Finally, we demonstrate that these algorithms are effectively parallelizable with polylogarithmic depths. …

    nus Repository record for EFFICIENT ALGORITHMS FOR GEOMETRIC OPTIMIZATION AND SYMMETRIC CONE PROGRAMMING (opens in a new tab) Download file for EFFICIENT ALGORITHMS FOR GEOMETRIC OPTIMIZATION AND SYMMETRIC CONE PROGRAMMING (opens in a new tab)

  7. Parameterized complexity and polynomial-time approximation schemes

    … 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 …

    tamu Repository record for Parameterized complexity and polynomial-time approximation schemes (opens in a new tab)

  8. New Multiobjective Shortest Path Algorithms

    … technique from the literature to obtain a new FPTAS for the MOSP problem. The resulting MD-FPTAS works also for multiobjective instances of the Time-Dependent Shortest Path problem, which is a novelty. Finally, we use the MDA and its biobjective version, the BDA, to solve the Multiobjective …

    fu-berlin Repository record for New Multiobjective Shortest Path Algorithms (opens in a new tab)

  9. Minimum Shared-Power Edge Cut

    … a fully polynomial time approximation scheme (FPTAS) for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational …

    waterloo Repository record for Minimum Shared-Power Edge Cut (opens in a new tab)

  10. Behaviorally-Informed Discrete Choice Models in Operations Management

    … a Fully Polynomial Time Approximation Scheme (FPTAS) that achieves near-optimal solutions efficiently. The third study introduces a discrete choice model that captures multi-product and multi-unit purchases and provides exact and approximate algorithms for assortment and pricing optimization. …

    queens Repository record for Behaviorally-Informed Discrete Choice Models in Operations Management (opens in a new tab)

  11. Approximation algorithms for linear programs and geometrically constrained packing roblems

    … We use the implementation in the context of an AFPTAS for Strip Packing in order to evaluate dynamic optimization of a parameter in the algorithm, namely the step length used for interpolation. We compare our choice to the static step length proposed in the analysis of the algorithm and conclude …

    cau-kiel Repository record for Approximation algorithms for linear programs and geometrically constrained packing roblems (opens in a new tab)

  12. Contracts for Density and Packing Functions

    … finite multiplicative approximation or additive FPTAS unless P=NP. On a positive note, Deo-Campo Vuong et al. provided an additive PTAS for the case when all agents have the same cost. Deo-Campo Vuong et al. asked whether an additive PTAS can be obtained for the general case, i.e for the case …

    waterloo Repository record for Contracts for Density and Packing Functions (opens in a new tab)

  13. Strategic Optimization Techniques For FRTU Deployment and Chip Physical Design

    … fully polynomial time approximation scheme (FPTAS) is proposed for the delay driven discrete gate sizing problem, which explores the theoretical view since the existing works are heuristics with no performance guarantee. The intellectual contribution of the proposed methods establishes a …

    mtu Repository record for Strategic Optimization Techniques For FRTU Deployment and Chip Physical Design (opens in a new tab)

  14. An Integrated Real-Time and Security Scheduling Framework for CPS

    … a fully polynomial time approximation scheme (FPTAS) that reduces the time complexity of solving the knapsack problem from a pseudo-polynomial to a fully polynomial. We also experiment with a greedy-heuristic approach and compare the results of both algorithms.

    vt Repository record for An Integrated Real-Time and Security Scheduling Framework for CPS (opens in a new tab)

  15. Modeling Context-Adaptive Energy-Aware Security in Mobile Devices

    … is a Fully Polynomial Time Approximation Scheme (FPTAS) which has a polynomial time execution complexity as opposed to the pseudo-polynomialDP based approach. To the best of the researcher’s knowledge, this is the first work focused on modeling, design, implementation and experimental performance.

    unf Repository record for Modeling Context-Adaptive Energy-Aware Security in Mobile Devices (opens in a new tab) Download PDF for Modeling Context-Adaptive Energy-Aware Security in Mobile Devices (opens in a new tab)

  16. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems

    … fully-polynomial-time approximation schemes (FPTAS) for allocating processing resource to components scheduled by earliest-deadline-first (EDF) or fixed-priority (FP) scheduling algorithm. For enforcing temporal isolation of demand-based interfaces, we provide a parametric approximate …

    wayne-thes Repository record for Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems (opens in a new tab)

  17. Static Risk Sensitive Reinforcement Learning

    … fully polynomial-time approximation scheme (FPTAS) algorithms to optimize entropic-based risk MDPs. 3) We propose practical VaR RL algorithms with performance bounds and convergence analysis.These contributions are based on three peer-reviewed conference publications. By addressing both …

    unh-thes Repository record for Static Risk Sensitive Reinforcement Learning (opens in a new tab)

  18. New Challenges in Revenue Management for Modern Marketplaces

    … a fully polynomial-time approximation scheme (FPTAS) for the randomized case and a $1/2$-approximate pseudo-polynomial algorithm for the deterministic case.

    cornell Repository record for New Challenges in Revenue Management for Modern Marketplaces (opens in a new tab)

  19. Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment

    … knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

    waterloo Repository record for Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment (opens in a new tab)

  20. Frontiers In Operations Research For Overcoming Barriers To Vehicle Electrification

    … a Fully Polynomial Time Approximation Scheme (FPTAS). From a theoretic perspective, the proposed two-phase approaches improve the state-of-the-art to optimally solving shortest path problems on general constrained multi-graph networks. These novel approaches are scalable and offer broad …

    wayne-thes Repository record for Frontiers In Operations Research For Overcoming Barriers To Vehicle Electrification (opens in a new tab)

Page 1 of 2