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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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. …
-
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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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 …
-
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 …
-
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.
-
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.
-
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 …
-
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 …
-
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.
-
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.
-
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 …
Page 1 of 2