Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs by Halman, Nir, Klabjan, Diego, Li, Chung-Lun, Orlin, James B, Simchi-Levi, David

“…We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. …”
Get full text
Get full text
Get full text

Fully polynomial time approximation schemes for sequential decision problems by Mostagir, Mohamed

Get full text

Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem by Yen Hung Chen

“…In this paper, we present two polynomial time approximation schemes (PTASs) for the constrained minimum spanning tree problem.…”
Get full text

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs by Borradaile, Glencora, Demaine, Erik D., Tazari, Siamak

“…We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded-genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. …”
Get full text
Get full text

An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs by Tu Jianhua, Shi Yongtang

“…Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the V C P3problem on planar graphs.…”
Get full text

Parallel-Batch Scheduling With Deterioration and Group Technology by Cuixia Miao

Subjects: Get full text

Energy-efficient allocation for multiple tasks in mobile edge computing by Jun Liu, Xi Liu

Subjects: Get full text

A PTAS For The k-Consensus Structures Problem Under Squared Euclidean Distance by Louxin Zhang, Yen Kaow Ng, Shuai Cheng Li

Subjects: Get full text

Maximizing the Number of Visible Labels on a Rotating Map by Ali Gholami Rudi

Subjects:

On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths by Borisovsky Pavel, Eremeev Anton, Hrushev Sergei, Teplyakov Vadim, Vorozhtsov Mikhail

Subjects: Get full text

A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions by Xiaofang Zhao, Shuguang Li

Subjects: Get full text

Approximation of Euclidean k-size cycle cover problem by Michael Khachay, Katherine Neznakhina

Subjects: Get full text

An Approach to Web Services Selection for Multiple Users by Wenlong Zhu, Beibei Yin, Siqian Gong, Kai-Yuan Cai

Subjects: “…Advanced a-fully polynomial time approximation scheme…”
Get full text

An FPTAS for the fractional group Steiner tree problem by Slobodan Jelić

Subjects: Get full text

Scheduling of Jobs with Multiple Weights on a Single Machine for Minimizing the Total Weighted Number of Tardy Jobs by Shuen Guo, Hao Lang, Hanxiang Zhang

“…We show in this paper that, in the case where <i>m</i> is a fixed number, the two problems are solvable in pseudo-polynomial time, the feasibility problem admits a dual-fully polynomial-time approximation scheme, and the Pareto-scheduling problem admits a fully polynomial-time approximation scheme.…”
Get full text

Guarding terrains via local search by Erik Krohn, Matt Gibson, Gaurav Kanade, Kasturi Varadarajan

“…We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. …”
Get full text

Constant inapproximability for Fisher markets by Deligkas, A, Fearnley, J, Hollender, A, Melissourgos, T

“…This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD = P. In fact, we prove that computing any approximation better than 1/11 is PPAD-complete. …”

Channel assignment on graphs of bounded treewidth. by McDiarmid, C, Reed, B

“…We show that this problem is NP-complete for graphs of treewidth at most 3, but there is a fully polynomial time approximation scheme for the problem on graphs of bounded treewidth. …”

RSU deployment planning based on approximation algorithm in urban VANET by Junyu ZHU, Chuanhe HUANG, Xiying FAN, Kuangyu QIN, Bin FU

“…To minimize the number of RSU deployed to cover a specific area,a c street model transforming the area covering problem to streets covering problem was designed,and a greedy-based polynomial (GBP) time approximation algorithm was developed to obtain the optimal RSU deployment for area coverage.For complex urban environments,a Cue model (complex urban environments model) was proposed.In this model,the target area was divided into different partitions.Then,based on shifting strategy,a polynomial time approximation scheme was designed.Theoretical analysis that include the approximation ratio and time complexity of the proposed algorithm were also presented.Simulation results show that GBP can efficiently solve the coverage problem in urban VANET.…”
Get full text

Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs by Ryan L. Mann, Michael J. Bremner

“…We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. …”
Get full text