Search results for "LP-rounding"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Zheng Fang, Jie Wang	Convex Combination Approximation for the Min-Cost WSN Point Coverage Problem.	WASA	2008	DBLP DOI BibTeX RDF	point coverage, minimum set multicover, approximation algorithm, sensor deployment, LP-rounding
2	Mohammad Khairul Hasan, Hyunwoo Jung, Kyung-Yong Chwa	Approximation algorithms for connected facility location problems.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Approximation algorithms, Integer programming, Steiner tree, LP-rounding, Connected facility location
2	Alexander Grigoriev, Maxim Sviridenko, Marc Uetz	LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
2	Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke, Uwe T. Zimmermann	On Minimum k-Modal Partitions of Permutations.	LATIN	2006	DBLP DOI BibTeX RDF	monotone sequence, k-modal sequence, cocoloring, approximation algorithm, online algorithm, Mixed integer program, hardness, LP rounding
1	Jaroslaw Byrka, MohammadReza Ghodsi, Aravind Srinivasan	LP-rounding algorithms for facility-location problems	CoRR	2010	DBLP BibTeX RDF
1	Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy	Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm	CoRR	2010	DBLP BibTeX RDF
1	Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy	Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm.	IPCO	2010	DBLP DOI BibTeX RDF
1	Saurav Pandit, Sriram V. Pemmaraju	Rapid randomized pruning for fast greedy distributed algorithms.	PODC	2010	DBLP DOI BibTeX RDF	distributed algorithms, randomized algorithms, greedy algorithms, facility location, primal-dual algorithms, minimum dominating set
1	Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson	Approximating the smallest k-edge connected spanning subgraph by LP-rounding.	Networks	2009	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled	On the set multi-cover problem in geometric settings.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	set cover, cuttings, LP rounding
1	Dong-Hoon Shin, Saurabh Bagchi	Optimal monitoring in multi-channel multi-radio wireless mesh networks.	MobiHoc	2009	DBLP DOI BibTeX RDF	lp rounding, multi-channel multi-radio wireless networks, approximation algorithm, wireless mesh networks, security monitoring
1	Siddharth Barman, Shuchi Chawla	Packing multiway cuts in capacitated graphs.	SODA	2009	DBLP DOI BibTeX RDF
1	Rajiv Gandhi, Julián Mestre	Combinatorial Algorithms for Data Migration to Minimize Average Completion Time.	Algorithmica	2009	DBLP DOI BibTeX RDF	Min-sum scheduling problems, Approximation algorithms, Primal-dual algorithms
1	Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai	Improved bounds for scheduling conflicting jobs with minsum criteria.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	sum multicoloring, scheduling, Approximation algorithms, linear programming, coloring, LP rounding
1	Chaitanya Swamy, David B. Shmoys	Fault-tolerant facility location.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	Approximation algorithms, facility location, k-median problem
1	Tim Carnes, David B. Shmoys	Primal-Dual Schema for Capacitated Covering Problems.	IPCO	2008	DBLP DOI BibTeX RDF
1	Anupam Gupta, R. Ravi, Amitabh Sinha	LP Rounding Approximation Algorithms for Stochastic Network Design.	Math. Oper. Res.	2007	DBLP DOI BibTeX RDF
1	Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson	Approximation algorithms for prize collecting forest problems with submodular penalty functions.	SODA	2007	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
1	Yuri Breitbart, Minos N. Garofalakis, Anupam Gupta, Amit Kumar, Rajeev Rastogi	On Configuring BGP Route Reflectors.	COMSWARE	2007	DBLP DOI BibTeX RDF
1	Mohammad Khairul Hasan, Hyunwoo Jung, Kyung-Yong Chwa	Improved Approximation Algorithm for Connected Facility Location Problems.	COCOA	2007	DBLP DOI BibTeX RDF
1	Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni	Robust Combinatorial Optimization with Exponential Scenarios.	IPCO	2007	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Aranyak Mehta, Atri Rudra	Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations.	WAOA	2007	DBLP DOI BibTeX RDF
1	Alexander Grigoriev, Maxim Sviridenko, Marc Uetz	Machine scheduling with resource dependent processing times.	Math. Program.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90B35, 68Q25, 68M20
1	Guang Xu, Jinhui Xu	Constant Approximation Algorithms for Rectangle Stabbing and Related Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
1	Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter	Quorum placement in networks: minimizing network congestion.	PODC	2006	DBLP DOI BibTeX RDF	congestion problems, approximation algorithms, Quorum systems, LP rounding
1	Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai	Improved results for data migration and open shop scheduling.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	open shop, scheduling, Approximation algorithms, linear programming, data migration, LP rounding
1	Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko	Tight approximation algorithms for maximum general assignment problems.	SODA	2006	DBLP DOI BibTeX RDF
1	Harold N. Gabow	Upper degree-constrained partial orientations.	SODA	2006	DBLP DOI BibTeX RDF
1	Mohammad Taghi Hajiaghayi, Kamal Jain	The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema.	SODA	2006	DBLP DOI BibTeX RDF
1	Noriyuki Fujimoto, Kenichi Hagihara	A 2-Approximation Algorithm for Scheduling Independent Tasks onto a Uniform Parallel Machine and its Extension to a Computational Grid.	CLUSTER	2006	DBLP DOI BibTeX RDF
1	Rajiv Gandhi, Julián Mestre	Combinatorial Algorithms for Data Migration to Minimize Average Completion Time.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	R. Ravi, Amitabh Sinha	Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (1991) 20E28, 20G40, 20C20
1	Guang Xu, Jinhui Xu	An LP rounding algorithm for approximating uncapacitated facility location problem with penalties.	Inf. Process. Lett.	2005	DBLP DOI BibTeX RDF
1	Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson	Approximating the smallest k-edge connected spanning subgraph by LP-rounding.	SODA	2005	DBLP DOI BibTeX RDF
1	Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter	Quorum placement in networks to minimize access delays.	PODC	2005	DBLP DOI BibTeX RDF	approximation algorithms, location, quorum systems, problems, LP rounding
1	Retsef Levi, Robin Roundy, David B. Shmoys	A constant approximation algorithm for the one-warehouse multi-retailer problem.	SODA	2005	DBLP DOI BibTeX RDF
1	Jian Tang, Guoliang Xue, Christopher Chandler, Weiyi Zhang	Link Scheduling with Power Control for Throughput Enhancement in Multihop Wireless Networks.	QSHINE	2005	DBLP DOI BibTeX RDF	QoS, fairness, power control, Cross-layer optimization, link scheduling
1	Alexander Grigoriev, Maxim Sviridenko, Marc Uetz	Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times.	IPCO	2005	DBLP DOI BibTeX RDF
1	Refael Hassin, Danny Segev	The Multi-radius Cover Problem.	WADS	2005	DBLP DOI BibTeX RDF
1	Asaf Levin, Danny Segev	Partial Multicuts in Trees.	WAOA	2005	DBLP DOI BibTeX RDF
1	Anupam Gupta, R. Ravi, Amitabh Sinha	An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.	FOCS	2004	DBLP DOI BibTeX RDF
1	David B. Shmoys, Chaitanya Swamy, Retsef Levi	Facility location with Service Installation Costs.	SODA	2004	DBLP DOI BibTeX RDF
1	Reuven Bar-Yehuda, Keren Bendel, Ari Freund, Dror Rawitz	Local ratio: A unified framework for approxmation algrithms in memoriam: Shimon Even 1935-2004.	ACM Comput. Surv.	2004	DBLP DOI BibTeX RDF	fractional local ratio, local ratio technique, Approximation algorithms
1	R. Ravi, Amitabh Sinha	Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems.	IPCO	2004	DBLP DOI BibTeX RDF
1	Toshihiro Fujito	On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	covering integer program, approximation algorithm, combinatorial optimization, partial cover
1	Chandra Chekuri, Sanjeev Khanna	Edge disjoint paths revisited.	SODA	2003	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Sudipto Guha, Joseph Naor	Approximating Steiner k-Cuts.	ICALP	2003	DBLP DOI BibTeX RDF	Multiway Cut, $k$-Cut, Steiner tree, minimum cut, primal-dual
1	Amit Kumar, Rajeev Rastogi, Abraham Silberschatz, Bülent Yener	Algorithms for provisioning virtual private networks in the hose model.	IEEE/ACM Trans. Netw.	2002	DBLP DOI BibTeX RDF	approximation algorithms, steiner trees, provisioning, virtual private networks, primal-dual algorithms, facility location problem, LP rounding, bandwidth utilization, hose model
1	Sudipto Guha, Kamesh Munagala	Improved algorithms for the data placement problem.	SODA	2002	DBLP DOI BibTeX RDF
1	Maxim Sviridenko	An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.	IPCO	2002	DBLP BibTeX RDF
1	David B. Shmoys	Approximation algorithms for facility location problems.	APPROX	2000	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Alan M. Frieze, Haim Kaplan	A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems.	FOCS	1996	DBLP DOI BibTeX RDF	rounding procedure, dense graph arrangement, randomized procedure, fractional perfect matchings, LP rounding procedure, assignment problem, randomised algorithms, linear inequality