Search results for "PTAS"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
113	Constantinos Daskalakis, Christos H. Papadimitriou	On oblivious PTAS's for nash equilibrium.	STOC	2009	DBLP DOI BibTeX RDF	anonymous games, oblivious algorithms, PTAS, bimatrix games
67	Zhao Zhang 0002, Xiaofeng Gao 0001, Weili Wu 0001, Ding-Zhu Du	PTAS for Minimum Connected Dominating Set in Unit Ball Graph.	WASA	2008	DBLP DOI BibTeX RDF	wireless sensor network, connected dominating set, unit ball graph
67	Xiuzhen Huang, Jianer Chen	On PTAS for Planar Graph Problems.	IFIP TCS	2006	DBLP DOI BibTeX RDF
65	Aleksei V. Fishkin, Klaus Jansen, Monaldo Mastrolilli	On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates.	ISAAC	2003	DBLP DOI BibTeX RDF	scheduling, Approximation, PTAS, job shop
59	Zhi-Zhong Chen, Lusheng Wang 0001, Zhanyong Wang	Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats.	Algorithmica	2009	DBLP DOI BibTeX RDF	Duplication models, Approximation algorithms, Tandem repeats
59	Artur Czumaj, Andrzej Lingas	Fast Approximation Schemes for Euclidean Multi-connectivity Problems.	ICALP	2000	DBLP DOI BibTeX RDF
58	MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx	Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth.	STOC	2010	DBLP DOI BibTeX RDF	Steiner forest, bounded-genus graphs, bounded-treewidth graphs, planar graphs, PTAS, series-parallel graphs
55	Tim Nieberg, Johann L. Hurink	A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs.	WAOA	2005	DBLP DOI BibTeX RDF
55	Clint Hepner, Clifford Stein 0001	Implementation of a PTAS for Scheduling with Release Dates.	ALENEX	2001	DBLP DOI BibTeX RDF
53	Yuzhong Zhang, Zhigang Cao 0002	An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Non-identical job sizes, Asymptotic PTAS, Scheduling, Makespan, Batching
48	Marta Z. Kwiatkowska, Gethin Norman, David Parker 0001	Stochastic Games for Verification of Probabilistic Timed Automata.	FORMATS	2009	DBLP DOI BibTeX RDF
48	Hadas Shachnai, Tami Tamir	Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
48	Chandra Chekuri, Sanjeev Khanna	Approximation schemes for preemptive weighted flow time.	STOC	2002	DBLP DOI BibTeX RDF
46	Bin Fu, Yumei Huo, Hairong Zhao	Makespan Minimization with Machine Availability Constraints.	COCOA	2009	DBLP DOI BibTeX RDF	machine availability constraints, makespan, PTAS, inapproximation
43	Joseph S. B. Mitchell	A PTAS for TSP with neighborhoods among fat regions in the plane.	SODA	2007	DBLP BibTeX RDF
43	Khaled M. Elbassioni, René Sitters, Yan Zhang 0021	A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs.	ESA	2007	DBLP DOI BibTeX RDF
43	Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos	Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
43	Chandra Chekuri, Sanjeev Khanna	A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.	ICALP	2001	DBLP DOI BibTeX RDF	average completion time, uniformly related machines, weighted completion time, scheduling, Polynomial time approximation scheme
36	Elad Hazan, Robert Krauthgamer	How hard is it to approximate the best Nash equilibrium?	SODA	2009	DBLP DOI BibTeX RDF
36	Jianping Li 0007, Weidong Li 0002, Jianbo Li	Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision.	COCOA	2009	DBLP DOI BibTeX RDF	Scheduling, allocation, polynomial time approximation scheme, fully polynomial time approximation scheme, grade of service
36	Hadas Shachnai, Tami Tamir, Omer Yehezkely	Approximation Schemes for Packing with Item Fragmentation.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Item fragmentation, Algorithms, Linear programming, Bin packing, Polynomial time approximation schemes
36	Monaldo Mastrolilli, Ola Svensson	(Acyclic) JobShops are Hard to Approximate.	FOCS	2008	DBLP DOI BibTeX RDF
36	Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden	Truthful Approximation Schemes for Single-Parameter Agents.	FOCS	2008	DBLP DOI BibTeX RDF
36	Liming Cai, Michael R. Fellows, David W. Juedes, Frances A. Rosamond	The Complexity of Polynomial-Time Approximation.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
36	Hadas Shachnai, Tami Tamir, Omer Yehezkely	Approximation Schemes for Packing with Item Fragmentation.	WAOA	2005	DBLP DOI BibTeX RDF
36	Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala	Tensor decomposition and approximation schemes for constraint satisfaction problems.	STOC	2005	DBLP DOI BibTeX RDF	approximation scheme, tensor decomposition
36	Leah Epstein, Tamir Tassa	Approximation schemes for the Min-Max Starting Time Problem.	Acta Informatica	2004	DBLP DOI BibTeX RDF
36	Murali K. Ganapathy, Sachin Lodha	On Minimum Circular Arrangement.	STACS	2004	DBLP DOI BibTeX RDF
36	Artur Czumaj, Andrzej Lingas, Hairong Zhao	Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem.	ICALP	2002	DBLP DOI BibTeX RDF
36	John E. Augustine, Steven S. Seiden	Linear Time Approximation Schemes for Vehicle Scheduling.	SWAT	2002	DBLP DOI BibTeX RDF
34	Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Ioannis Lambadaris, Lata Narayanan, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia, Mohammadreza Yazdani	On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment.	ADHOC-NOW	2009	DBLP DOI BibTeX RDF	Intruder, Optimal Movement, Sensors, NP-complete, Coverage, Detection, PTAS, Barrier, Line Segment
34	Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips	Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance.	Algorithmica	2008	DBLP DOI BibTeX RDF	Manhattan distance, Clustering, Approximation, Supercomputers, Communication cost, Processor allocation, Polynomial-time approximation scheme (PTAS)
34	Omid Amini, Stéphane Pérennes, Ignasi Sau	Hardness and Approximation of Traffic Grooming.	ISAAC	2007	DBLP DOI BibTeX RDF	SONET ADM, Approximation Algorithms, Optical Networks, PTAS, inapproximability, Traffic Grooming, APX-hardness
34	Matthias Müller-Hannemann, Siamak Tazari	A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane.	WADS	2007	DBLP DOI BibTeX RDF	Uniform Orientation Metric, Banyan, Planar Graph, Steiner Tree, Spanner, PTAS, Obstacles, Euclidean Metric
34	Ashkan Aazami, Michael D. Stilp	Approximation Algorithms and Hardness for Domination with Propagation.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF	Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS
34	Amitai Armon, Yossi Azar, Leah Epstein	Temporary Tasks Assignment Resolved.	Algorithmica	2003	DBLP DOI BibTeX RDF	Unrelated machines, Load balancing, Competitive, On-line, PTAS
31	Anna Adamaszek, Artur Czumaj, Andrzej Lingas	PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k.	ISAAC	2009	DBLP DOI BibTeX RDF
31	Nabil H. Mustafa, Saurabh Ray	PTAS for geometric hitting set problems via local search.	SCG	2009	DBLP DOI BibTeX RDF	approximation algorithm, local search, hitting sets, epsilon nets
31	Tim Nonner, Alexander Souza	Latency Constrained Aggregation in Chain Networks Admits a PTAS.	AAIM	2009	DBLP DOI BibTeX RDF
31	Christian Glaßer, Christian Reitwießner, Heinz Schmitz	Multiobjective Disk Cover Admits a PTAS.	ISAAC	2008	DBLP DOI BibTeX RDF
31	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs.	MFCS	2008	DBLP DOI BibTeX RDF
31	Shuai Cheng Li 0001, Yen Kaow Ng, Louxin Zhang	A PTAS for the k-Consensus Structures Problem Under Euclidean Squared Distance.	FAW	2008	DBLP DOI BibTeX RDF
31	Andreas Wiese, Evangelos Kranakis	Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs.	DCOSS	2008	DBLP DOI BibTeX RDF
31	Dan Feldman, Morteza Monemizadeh, Christian Sohler	A PTAS for k-means clustering based on weak coresets.	SCG	2007	DBLP DOI BibTeX RDF	approximation, k-mean, geometric optimization, coresets
31	Yuzhong Zhang, Zhigang Cao	An Asymptotic PTAS for Batch Scheduling with Nonidentical Job Sizes to Minimize Makespan.	COCOA	2007	DBLP DOI BibTeX RDF
31	Xiaotie Deng, Haodi Feng, Guojun Li, Benyun Shi	A PTAS for Semiconductor Burn-in Scheduling.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	geometric rounding, time stretching, approximation algorithm, batch processing, release date
31	Yuzhong Zhang, Zhigang Cao, Qingguo Bai	A PTAS for Scheduling on Agreeable Unrelated Parallel Batch Processing Machines with Dynamic Job Arrivals.	AAIM	2005	DBLP DOI BibTeX RDF
31	Subhash Khot	Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.	FOCS	2004	DBLP DOI BibTeX RDF
31	Mao-cheng Cai, Xiaotie Deng, Haodi Feng, Guojun Li, Guizhen Liu	A PTAS for Minimizing Total Completion Time of Bounded Batch Scheduling.	IPCO	2002	DBLP DOI BibTeX RDF
24	Amotz Bar-Noy, Panagiotis Cheilaris, Yi Feng 0002, Asaf Levin	Finding mobile data under delay constraints with searching costs.	PODC	2010	DBLP DOI BibTeX RDF	partitioning and scheduling, approximation algorithms, design and analysis of algorithms
24	Eric Angel, Evripidis Bampis, Fanny Pascual, Alex-Ariel Tchetgnia	On truthfulness and approximation for scheduling selfish tasks.	J. Sched.	2009	DBLP DOI BibTeX RDF	Scheduling, Approximation algorithms, Game theory, Truthfulness
24	Imran A. Pirwani	Shifting Strategy for Geometric Graphs without Geometry.	ISAAC	2009	DBLP DOI BibTeX RDF
24	Cristina Bazgan, Basile Couëtoux, Zsolt Tuza	Covering a Graph with a Constrained Forest (Extended Abstract).	ISAAC	2009	DBLP DOI BibTeX RDF
24	Klaus Jansen	Parameterized approximation scheme for the multiple knapsack problem.	SODA	2009	DBLP DOI BibTeX RDF
24	Avner Magen, Mohammad Moharrami	Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
24	Leah Epstein, Rob van Stee	Maximizing the Minimum Load for Selfish Agents.	LATIN	2008	DBLP DOI BibTeX RDF
24	Maria Liazi, Ioannis Milis, Fanny Pascual, Vassilis Zissimopoulos	The densest k-subgraph problem on clique graphs.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Densest k-subgraph, Clique graph, Dynamic programming, Polynomial time approximation scheme
24	Florian Diedrich, Klaus Jansen, Fanny Pascual, Denis Trystram	Approximation Algorithms for Scheduling with Reservations.	HiPC	2007	DBLP DOI BibTeX RDF
24	Dániel Marx	On the Optimality of Planar and Geometric Approximation Schemes.	FOCS	2007	DBLP DOI BibTeX RDF
24	André Berger, Michelangelo Grigni	Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
24	Kuen-Lin Yu, Chung-Shou Liao, D. T. Lee	Maximizing the Number of Independent Labels in the Plane.	FAW	2007	DBLP DOI BibTeX RDF
24	Jan Remy, Reto Spöhel, Andreas Weißl	On Euclidean Vehicle Routing with Allocation.	WADS	2007	DBLP DOI BibTeX RDF
24	Claire Kenyon-Mathieu, Warren Schudy	How to rank with few errors.	STOC	2007	DBLP DOI BibTeX RDF	Kemeny-Young rank aggregation, feedback arc set, max acyclic subgraph, tournament graphs, approximation algorithm, polynomial-time approximation scheme
24	Lusheng Wang 0001, Zhanyong Wang, Zhi-Zhong Chen	Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats.	COCOON	2007	DBLP DOI BibTeX RDF
24	Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella	The Freeze-Tag Problem: How to Wake Up a Swarm ofRobots.	Algorithmica	2006	DBLP DOI BibTeX RDF
24	Jens Gramm, Jiong Guo, Rolf Niedermeier	Parameterized Intractability of Distinguishing Substring Selection.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
24	Ioannis Giotis 0001, Venkatesan Guruswami	Correlation clustering with a fixed number of clusters.	SODA	2006	DBLP DOI BibTeX RDF
24	Erik Jan van Leeuwen	Better Approximation Schemes for Disk Graphs.	SWAT	2006	DBLP DOI BibTeX RDF
24	Xiuzhen Huang	Lower Bounds and Parameterized Approach for Longest Common Subsequence.	COCOON	2006	DBLP DOI BibTeX RDF
24	Rajeev Alur, Swarat Chaudhuri	Branching Pushdown Tree Automata.	FSTTCS	2006	DBLP DOI BibTeX RDF
24	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Tao Jiang 0001	Correlation Clustering and Consensus Clustering.	ISAAC	2005	DBLP DOI BibTeX RDF
24	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.	SODA	2005	DBLP BibTeX RDF
24	Brona Brejová, Daniel G. Brown 0001, Ian M. Harrower, Alejandro López-Ortiz, Tomás Vinar	Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern.	CPM	2005	DBLP DOI BibTeX RDF
24	Dániel Marx	Efficient Approximation Schemes for Geometric Problems?.	ESA	2005	DBLP DOI BibTeX RDF
24	Andreas Björklund	Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs.	ESA	2005	DBLP DOI BibTeX RDF
24	Michael A. Bender, S. Muthukrishnan 0001, Rajmohan Rajaraman	Approximation Algorithms for Average Stretch Scheduling.	J. Sched.	2004	DBLP DOI BibTeX RDF	average stretch, approximation algorithms, Scheduling algorithms
24	Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, Riccardo Silvestri	Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks.	STACS	2004	DBLP DOI BibTeX RDF
24	Hadas Shachnai, Oded Shmueli, Robert Sayegh	Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints.	WAOA	2004	DBLP DOI BibTeX RDF
24	Yen Hung Chen, Bang Ye Wu, Chuan Yi Tang	Approximation Algorithms for k-Source Bottleneck Routing Cost Spanning Tree Problems.	ICCSA (3)	2004	DBLP DOI BibTeX RDF	approximation algorithm, spanning tree, polynomial time approximation scheme, Combinatorial optimization problem
24	Moses Charikar, Venkatesan Guruswami, Anthony Wirth	Clustering with Qualitative Information.	FOCS	2003	DBLP DOI BibTeX RDF
24	Alberto Caprara, Andrea Lodi 0001, Michele Monaci	An Approximation Scheme for the Two-Stage, Two-Dimensional Bin Packing Problem.	IPCO	2002	DBLP DOI BibTeX RDF
24	Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella	The freeze-tag problem: how to wake up a swarm of robots.	SODA	2002	DBLP BibTeX RDF
24	Piotr Berman, Marek Karpinski	Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION.	ICALP	2002	DBLP DOI BibTeX RDF
24	Binhai Zhu	Approximating 3D Points with Cylindrical Segments.	COCOON	2002	DBLP DOI BibTeX RDF
24	Markus Bläser, Bodo Siebert	Computing Cycle Covers without Short Cycles.	ESA	2001	DBLP DOI BibTeX RDF
24	Hadas Shachnai, Tami Tamir	Polynominal time approximation schemes for class-constrained packing problem.	APPROX	2000	DBLP DOI BibTeX RDF
24	Tao Jiang 0001, Paul E. Kearney, Ming Li 0001	Orchestrating Quartets: Approximation and Data Correction.	FOCS	1998	DBLP DOI BibTeX RDF	quartet, approximation, recombination, evolutionary tree, cleaning
22	Balabhaskar Balasundaram, Sergiy Butenko	Optimization Problems in Unit-Disk Graphs.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Coloring, Dominating sets, Independent sets, PTAS, Cliques, Unit-disk graphs
22	Tim Nieberg, Johann L. Hurink, Walter Kern	Approximation schemes for wireless networks.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	bounded growth, Wireless ad-hoc networks, PTAS, maximum independent set, minimum dominating set
22	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh 0001	Degree-Constrained Subgraph Problems: Hardness and Approximation Results.	WAOA	2008	DBLP DOI BibTeX RDF	Degree-Constrained Subgraphs, Apx, Excluded Minor, Approximation Algorithms, Hardness of Approximation, PTAS
22	Yen Hung Chen, Gwo-Liang Liao, Chuan Yi Tang	Approximation Algorithms for 2-Source Minimum Routing Cost k -Tree Problems.	ICCSA (3)	2007	DBLP DOI BibTeX RDF	approximation algorithm, polynomial time approximation scheme (PTAS), combinatorial optimization problem, k-tree
22	Sándor P. Fekete, Henk Meijer	Maximum Dispersion and Geometric Maximum Weight Cliques.	Algorithmica	2004	DBLP DOI BibTeX RDF	Remote clique, Heaviest subgraph, Approximation, Facility location, PTAS, Geometric optimization, Dispersion, Maximum weight cliques
22	Kunal Talwar	Bypassing the embedding: algorithms for low dimensional metrics.	STOC	2004	DBLP DOI BibTeX RDF	TSP, PTAS, routing schemes, doubling metrics, distance labels
22	Tom Korsmeyer, Jun Zeng, Ken Greiner	Design tools for BioMEMS.	DAC	2004	DBLP DOI BibTeX RDF	BEM, CAD, MEMS, PTAS, FEM, system-level modeling, lab-on-a-chip, BioMEMS
22	Xiang-Yang Li 0001, Yu Wang 0003	Simple heuristics and PTASs for intersection graphs in wireless ad hoc networks.	DIAL-M	2002	DBLP DOI BibTeX RDF	disk graphs, wireless ad hoc networks, independent set, PTAS, vertex cover, vertex coloring
22	Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia	Optimal covering tours with turn costs.	SODA	2001	DBLP BibTeX RDF	m-guillotine subdivisions, lawn mowing, milling, turn costs, approximation algorithms, NP-completeness, traveling salesman problem (TSP), manufacturing, polynomial-time approximation scheme (PTAS), covering, NC machining
19	Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang	A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals.	SODA	2024	DBLP DOI BibTeX RDF
19	Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný	PTAS for Sparse General-valued CSPs.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
19	Claire Mathieu, Hang Zhou 0001	A PTAS for Capacitated Vehicle Routing on Trees.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
19	Miguel Bosch-Calvo, Fabrizio Grandoni 0001, Afrouz Jabal Ameli	A PTAS for Triangle-Free 2-Matching.	CoRR	2023	DBLP DOI BibTeX RDF