Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
11	Shuchi Chawla 0001, Jason D. Hartline, Robert D. Kleinberg	Algorithmic pricing via virtual valuations.	EC	2007	DBLP DOI BibTeX RDF	virtual valuations, approximation algorithms, pricing
11	Ioannis Caragiannis	Wavelength Management in WDM Rings to Maximize the Number of Connections.	STACS	2007	DBLP DOI BibTeX RDF
11	Viswanath Nagarajan, R. Ravi 0001	Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
11	Jérôme Monnot, Sophie Toulouse	The Pk Partition Problem and Related Problems in Bipartite Graphs.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
11	Yuli Ye, Allan Borodin	Priority Algorithms for the Subset-Sum Problem.	COCOON	2007	DBLP DOI BibTeX RDF
11	Emanuele Viola, Avi Wigderson	Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.	CCC	2007	DBLP DOI BibTeX RDF
11	John R. Douceur, Jay R. Lorch, Thomas Moscibroda	Maximizing total upload in latency-sensitive P2P applications.	SPAA	2007	DBLP DOI BibTeX RDF	peer-to-peer gaming, upload maximization, multicast
11	Julia Chuzhoy, Joseph Naor	New hardness results for congestion minimization and machine scheduling.	J. ACM	2006	DBLP DOI BibTeX RDF	resource minimization, scheduling, network routing, Hardness of approximation, congestion minimization
11	K. Subramani 0001, C. Tauras	An approximation algorithm for state minimization in 2-MDFAs.	Formal Aspects Comput.	2006	DBLP DOI BibTeX RDF	2-MDFA, Finite state automata, State minimization
11	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of edge dominating set problems.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Minimum edge dominating set, Minimum maximal matching, Approximation lower bound, Everywhere dense graphs, Bounded degree graphs
11	Venkatesan Guruswami	On 2-Query Codeword Testing with Near-Perfect Completeness.	ISAAC	2006	DBLP DOI BibTeX RDF
11	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	The price of being near-sighted.	SODA	2006	DBLP DOI BibTeX RDF
11	Stamatis Stefanakos	Reliable Routings in Networks with Generalized Link Failure Events.	Networking	2006	DBLP DOI BibTeX RDF
11	Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt	Approximation Schemes for First-Order Definable Optimisation Problems.	LICS	2006	DBLP DOI BibTeX RDF
11	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Giancarlo Mauri	Fingerprint Clustering with Bounded Number of Missing Values.	CPM	2006	DBLP DOI BibTeX RDF
11	Christopher Umans	Optimization Problems in the Polynomial-Time Hierarchy.	TAMC	2006	DBLP DOI BibTeX RDF
11	Subhash Khot, Ryan O'Donnell	SDP gaps and UGC-hardness for MAXCUTGAIN.	FOCS	2006	DBLP DOI BibTeX RDF
11	Christoph Ambühl, Monaldo Mastrolilli	Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.	ESA	2006	DBLP DOI BibTeX RDF
11	Jochen Könemann, Ojas Parekh, Danny Segev	A Unified Approach to Approximating Partial Covering Problems.	ESA	2006	DBLP DOI BibTeX RDF
11	Satish Rao, Shuheng Zhou	Edge Disjoint Paths in Moderately Connected Graphs.	ICALP (1)	2006	DBLP DOI BibTeX RDF
11	Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß	Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.	CIAC	2006	DBLP DOI BibTeX RDF
11	Hans L. Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, René Sitters, Thomas Wolle	On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems.	WAOA	2006	DBLP DOI BibTeX RDF	minimum corridor connection, generalized geometric problems, complexity, approximations, exact algorithms
11	Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie	An Approximation Algorithm for the Wireless Gathering Problem.	SWAT	2006	DBLP DOI BibTeX RDF
11	Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke 0001	Minimum Membership Set Covering and the Consecutive Ones Property.	SWAT	2006	DBLP DOI BibTeX RDF
11	Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke 0002, Guido Proietti, Peter Widmayer	Reusing Optimal TSP Solutions for Locally Modified Input Instances.	IFIP TCS	2006	DBLP DOI BibTeX RDF
11	Julia Chuzhoy, Sanjeev Khanna	Hardness of cut problems in directed graphs.	STOC	2006	DBLP DOI BibTeX RDF	directed multicut, hardness of approximation, sparsest cut
11	Nader H. Bshouty, Lynn Burroughs	Maximizing Agreements with One-Sided Error with Applications to Heuristic Learning.	Mach. Learn.	2005	DBLP DOI BibTeX RDF	maximizing agreements, heuristic learning, approximation, Boolean formulas, example-based learning, agnostic learning
11	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.	SODA	2005	DBLP BibTeX RDF
11	Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian	Complete partitions of graphs.	SODA	2005	DBLP BibTeX RDF
11	Christian Liebchen	A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables.	WEA	2005	DBLP DOI BibTeX RDF
11	Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten	Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack.	ESA	2005	DBLP DOI BibTeX RDF	min-max regret, mi-nimum spanning tree, approximation, shortest path, knapsack, min-max, fptas
11	Claude Chaudet, Eric Fleury, Isabelle Guérin Lassous, Hervé Rivano, Marie-Emilie Voge	Optimal positioning of active and passive monitoring devices.	CoNEXT	2005	DBLP DOI BibTeX RDF	optimization, active monitoring, passive monitoring
11	Thomas Moscibroda, Roger Wattenhofer	Facility location: distributed approximation.	PODC	2005	DBLP DOI BibTeX RDF	distributed approximation, linear programming, facility location, primal-dual algorithms
11	Gregor Gramlich, Georg Schnitger	Minimizing NFA's and Regular Expressions.	STACS	2005	DBLP DOI BibTeX RDF
11	Bodo Manthey	On Approximating Restricted Cycle Covers.	WAOA	2005	DBLP DOI BibTeX RDF
11	Bruno Escoffier, Vangelis Th. Paschos	Differential Approximation of min sat, max sat and Related Problems.	ICCSA (4)	2005	DBLP DOI BibTeX RDF
11	Venkatesan Guruswami, Luca Trevisan	The Complexity of Making Unique Choices: Approximating 1-in- k SAT.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
11	Luca Forlizzi, Juraj Hromkovic, Guido Proietti, Sebastian Seibert	On the Stability of Approximation for Hamiltonian Path Problems.	SOFSEM	2005	DBLP DOI BibTeX RDF
11	Xujin Chen, Xiao-Dong Hu 0001, Tianping Shuai	Routing and Coloring for Maximal Number of Trees.	COCOON	2005	DBLP DOI BibTeX RDF
11	Spyros Angelopoulos 0001, Allan Borodin	The Power of Priority Algorithms for Facility Location and Set Cover.	Algorithmica	2004	DBLP DOI BibTeX RDF	Approximation lower bounds, Greedy algorithms
11	Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier	Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
11	José R. Correa, Claire Kenyon	Approximation schemes for multidimensional packing.	SODA	2004	DBLP BibTeX RDF
11	Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor	Machine Minimization for Scheduling Jobs with Interval Constraints.	FOCS	2004	DBLP DOI BibTeX RDF
11	Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia	Polynomial Time Approximation Schemes and Parameterized Complexity.	MFCS	2004	DBLP DOI BibTeX RDF
11	Stavros G. Kolliopoulos, George Steiner	On Minimizing the Total Weighted Tardiness on a Single Machine.	STACS	2004	DBLP DOI BibTeX RDF
11	Toshihiro Fujito, Takatoshi Yabuta	Submodular Integer Cover and Its Application to Production Planning.	WAOA	2004	DBLP DOI BibTeX RDF
11	Alexander Grigoriev, Stan P. M. van Hoesel, Anton F. van der Kraaij, Marc Uetz, Mustapha Bouhtou	Pricing Network Edges to Cross a River.	WAOA	2004	DBLP DOI BibTeX RDF
11	Julia Chuzhoy, Joseph Naor	New hardness results for congestion minimization and machine scheduling.	STOC	2004	DBLP DOI BibTeX RDF	routing, approximation algorithms, hardness of approximation, machine scheduling, congestion minimization
11	Jiangzhuo Chen, Robert D. Kleinberg, László Lovász 0001, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta	(Almost) tight bounds and existence theorems for confluent flows.	STOC	2004	DBLP DOI BibTeX RDF	confluent flow, routing, approximation algorithms, network flow, tight bounds
11	Alessandro Panconesi, Mauro Sozio	Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction.	WABI	2004	DBLP DOI BibTeX RDF
11	Gustav Hast	Approximating Max kCSP Using Random Restrictions.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
11	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	Unit disk graph approximation.	DIALM-POMC	2004	DBLP DOI BibTeX RDF	sensor networks, ad hoc networks, embedding, unit disk graph, virtual coordinates
11	Jean Cardinal, Stefan Langerman	Designing Small Keyboards Is Hard.	LATIN	2004	DBLP DOI BibTeX RDF
11	Kirk Pruhs, Gerhard J. Woeginger	Approximation Schemes for a Class of Subset Selection Problems.	LATIN	2004	DBLP DOI BibTeX RDF
11	Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Pino Persiano	How to route and tax selfish unsplittable traffic.	SPAA	2004	DBLP DOI BibTeX RDF	scheduling, nash equilibrium, selfish routing, algorithmic mechanism design
11	Andrea E. F. Clementi, Paolo Penna, Afonso Ferreira, Stephane Perennes, Riccardo Silvestri	The Minimum Range Assignment Problem on Linear Radio Networks.	Algorithmica	2003	DBLP DOI BibTeX RDF
11	Vangelis Th. Paschos	Polynomial Approximation and Graph-Coloring.	Computing	2003	DBLP DOI BibTeX RDF	AMS Subject Classification: 05C15, 68Q17, 68Q25, 90C59, 68W25
11	Tomoyuki Yamakami	Computational Complexity Measures of Multipartite Quantum Entanglement.	ISAAC	2003	DBLP DOI BibTeX RDF
11	Richard Beigel, Lance Fortnow, Frank Stephan 0001	Infinitely-Often Autoreducible Sets.	ISAAC	2003	DBLP DOI BibTeX RDF
11	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching.	ISAAC	2003	DBLP DOI BibTeX RDF
11	Chandra Chekuri, Sanjeev Khanna	Edge disjoint paths revisited.	SODA	2003	DBLP BibTeX RDF
11	Jittat Fakcharoenphol, Chris Harrelson, Satish Rao	The k-traveling repairman problem.	SODA	2003	DBLP BibTeX RDF
11	Jianer Chen, Iyad A. Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia	Genus Characterizes the Complexity of Graph Problems: Some Tight Results.	ICALP	2003	DBLP DOI BibTeX RDF
11	Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos	Completeness in Differential Approximation Classes.	MFCS	2003	DBLP DOI BibTeX RDF
11	Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro	Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems.	IPDPS	2003	DBLP DOI BibTeX RDF
11	Patricia A. Evans, Andrew D. Smith	Complexity of Approximating Closest Substring Problems.	FCT	2003	DBLP DOI BibTeX RDF	Closest Substring, Approximation algorithms, Hardness of approximation
11	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness for Small Occurrence Instances of NP-Hard Problems.	CIAC	2003	DBLP DOI BibTeX RDF
11	Spyros Angelopoulos 0001	Randomized Priority Algorithms: (Extended Abstract).	WAOA	2003	DBLP DOI BibTeX RDF
11	Patrik Floréen, Petteri Kaski, Jukka Kohonen, Pekka Orponen	Multicast time maximization in energy constrained wireless networks.	DIALM-POMC	2003	DBLP DOI BibTeX RDF	Steiner tree packing, multi-hop packet networks, optimization, sensor networks, wireless networks, multicasting, energy saving
11	Johan Håstad	Inapproximability Some history and some open problems.	CCC	2003	DBLP DOI BibTeX RDF
11	Gagan Aggarwal, Rajeev Motwani 0001, An Zhu	The load rebalancing problem.	SPAA	2003	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, load balancing
11	Arnold L. Rosenberg	Optimal Schedules for Cycle-Stealing in a Network of Workstations with a Bag-of-Tasks Workload.	IEEE Trans. Parallel Distributed Syst.	2002	DBLP DOI BibTeX RDF	bag-of-tasks workloads, networks of workstations (NOWs), scheduling parallel computations, heavy-tailed distributions, optimal scheduling, Cycle-stealing
11	Ravi Ramamoorthi, Amitabh Sinha II	Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design.	IPCO	2002	DBLP DOI BibTeX RDF
11	Klaus Jansen, Lorant Porkolab	On Preemptive Resource Constrained Scheduling: Polynomial-Time Approximation Schemes.	IPCO	2002	DBLP DOI BibTeX RDF
11	Ojas Parekh	Edge dominating and hypomatchable sets.	SODA	2002	DBLP BibTeX RDF
11	Julia Chuzhoy, Joseph Naor	Covering Problems with Hard Capacities.	FOCS	2002	DBLP DOI BibTeX RDF
11	Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos	Weighted Node Coloring: When Stable Sets Are Expensive.	WG	2002	DBLP DOI BibTeX RDF
11	Klaus Jansen	Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling.	STACS	2002	DBLP DOI BibTeX RDF
11	Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra	On the complexity of equilibria.	STOC	2002	DBLP DOI BibTeX RDF
11	Kamal Jain, Mohammad Mahdian, Amin Saberi	A new greedy approach for facility location problems.	STOC	2002	DBLP DOI BibTeX RDF
11	Spyros Angelopoulos 0001, Allan Borodin	On the Power of Priority Algorithms for Facility Location and Set Cover.	APPROX	2002	DBLP DOI BibTeX RDF
11	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network-Design Problems.	APPROX	2002	DBLP DOI BibTeX RDF
11	Nitin Ahuja, Anand Srivastav	On Constrained Hypergraph Coloring and Scheduling.	APPROX	2002	DBLP DOI BibTeX RDF
11	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.	FSTTCS	2002	DBLP DOI BibTeX RDF	minimum-cost biconnected spanning subgraph, Approximation algorithm, inapproximability, augmentation
11	Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine	Winner determination in combinatorial auction generalizations.	AAMAS	2002	DBLP DOI BibTeX RDF
11	Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer	Inapproximability Results for Guarding Polygons and Terrains.	Algorithmica	2001	DBLP DOI BibTeX RDF
11	Guy Kortsarz	On the Hardness of Approximating Spanners.	Algorithmica	2001	DBLP DOI BibTeX RDF
11	Johan Håstad	Some optimal inapproximability results.	J. ACM	2001	DBLP DOI BibTeX RDF	NP-hard optimization problems, max-sat, linear equations, Inapproximability, probabilistically checkable proofs
11	Michael Elkin, David Peleg	Approximating k-Spanner Problems for k>2.	IPCO	2001	DBLP DOI BibTeX RDF
11	Benjamin Doerr	Lattice approximation and linear discrepency of totally unimodular matrices.	SODA	2001	DBLP BibTeX RDF
11	Alberto Caprara, Alessandro Panconesi, Romeo Rizzi	Packing Cycles and Cuts in Undirected Graphs.	ESA	2001	DBLP DOI BibTeX RDF
11	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
11	Foto N. Afrati, Ioannis Milis	Designing PTASs for MIN-SUM Scheduling Problems.	FCT	2001	DBLP DOI BibTeX RDF
11	Avrim Blum, Adam Kalai, Jon M. Kleinberg	Admission Control to Minimize Rejections.	WADS	2001	DBLP DOI BibTeX RDF
11	Alantha Newman	The Maximum Acyclic Subgraph Problem and Degree-3 Graphs.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
11	Andrea E. F. Clementi, Pierluigi Crescenzi, Angelo Monti, Paolo Penna, Riccardo Silvestri	On Computing Ad-hoc Selective Families.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
11	Evripidis Bampis, Rodolphe Giroudeau, Alexander V. Kononov	Scheduling tasks with small communication delays for clusters of processors.	SPAA	2001	DBLP DOI BibTeX RDF
11	John H. Reif	Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input.	Algorithmica	2000	DBLP DOI BibTeX RDF	Visibility problems, Gap-preserving reductions, Telecommunications, Terrains, Inapproximability, Art gallery
11	Charles Meyssonnier, Paolo Boldi, Sebastiano Vigna	delta-Approximable Functions.	CCA	2000	DBLP DOI BibTeX RDF
11	Robert D. Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh	A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem.	ESA	2000	DBLP DOI BibTeX RDF