Search results for "randomized rounding"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Lasse Kliemann, Anand Srivastav	Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching.	SEA	2009	DBLP DOI BibTeX RDF	hypergraph matching, approximation algorithms, greedy algorithms, hybrid algorithms, NP-hard problems, randomized rounding
3	Tobias Friedrich, Thomas Sauerwald	Near-perfect load balancing by randomized rounding.	STOC	2009	DBLP DOI BibTeX RDF	load balancing, randomized rounding
3	Benjamin Doerr, Henning Schnieder	Non-independent Randomized Rounding and an Application to Digital Halftoning.	ESA	2002	DBLP DOI BibTeX RDF	discrepancy, Randomized rounding, digital halftoning
3	Benjamin Doerr	Structured Randomized Rounding and Coloring.	FCT	2001	DBLP DOI BibTeX RDF	hypergraph coloring, randomized algorithms, integer linear programming, discrepancy, randomized rounding
2	Uriel Feige	On maximizing welfare when utility functions are subadditive.	STOC	2006	DBLP DOI BibTeX RDF	combinatorial auctions, randomized rounding
2	Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy 0002, Aravind Srinivasan	Dependent rounding and its applications to approximation algorithms.	J. ACM	2006	DBLP DOI BibTeX RDF	Randomized rounding, broadcast scheduling
2	Liang Yang, Tushar Gohad, Pavel Ghosh, Devesh Sinha, Arunabha Sen, Andréa W. Richa	Resource mapping and scheduling for heterogeneous network processor systems.	ANCS	2005	DBLP DOI BibTeX RDF	HW-SW partitioning, network processor, codesign, randomized rounding
2	Richard M. Karp, Claire Kenyon	A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
2	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan	An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.	ICALP	2003	DBLP DOI BibTeX RDF	capacitated covering, Approximation algorithms, linear programming, set cover, vertex cover, randomized rounding
2	D. Sivakumar	Algorithmic Derandomization via Complexity Theory. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	Johnson-Lindenstrauss Lemma, Derandomization, randomized rounding
2	Eran Halperin, Aravind Srinivasan	Improved Approximation Algorithms for the Partial Vertex Cover Problem.	APPROX	2002	DBLP DOI BibTeX RDF	Partial vertex cover, approximation algorithms, semidefinite programming, randomized rounding
2	Rajiv Gandhi, Samir Khuller, Aravind Srinivasan	Approximation Algorithms for Partial Covering Problems.	ICALP	2001	DBLP DOI BibTeX RDF	Approximation algorithms, set cover, vertex cover, randomized rounding, primal-dual methods, partial covering
1	Dongdong Ge, Simai He, Yinyu Ye, Jiawei Zhang	Geometric rounding: a dependent randomized rounding scheme.	J. Comb. Optim.	2011	DBLP DOI BibTeX RDF
1	Nicolò Cesa-Bianchi, Ohad Shamir	Efficient Online Learning via Randomized Rounding	CoRR	2011	DBLP BibTeX RDF
1	Benjamin Doerr, Marvin Künnemann, Magnus Wahlström	Dependent Randomized Rounding: The Bipartite Case.	ALENEX	2011	DBLP BibTeX RDF
1	Shayan Oveis Gharan, Amin Saberi, Mohit Singh	A Randomized Rounding Approach to the Traveling Salesman Problem.	FOCS	2011	DBLP DOI BibTeX RDF
1	Nicolò Cesa-Bianchi, Ohad Shamir	Efficient Online Learning via Randomized Rounding.	NIPS	2011	DBLP BibTeX RDF
1	Anna Huber	Randomized rounding and rumor spreading with stochastic dependencies.		2010	RDF
1	Mustapha Bouhtou, Stéphane Gaubert, Guillaume Sagnol	Submodularity and Randomized rounding techniques for Optimal Experimental Design.	Electronic Notes in Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Michael Gnewuch, Magnus Wahlström	Algorithmic construction of low-discrepancy point sets via dependent randomized rounding.	J. Complexity	2010	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Marvin Künnemann, Magnus Wahlström	Randomized Rounding for Routing and Covering Problems: Experiments and Improvements	CoRR	2010	DBLP BibTeX RDF
1	Benjamin Doerr, Marvin Künnemann, Magnus Wahlström	Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.	SEA	2010	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Jan Vondrák, Rico Zenklusen	Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.	FOCS	2010	DBLP DOI BibTeX RDF
1	Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità	An improved LP-based approximation for steiner tree.	STOC	2010	DBLP DOI BibTeX RDF	approximation algorithms, randomized algorithms, network design, linear programming relaxations
1	Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh	A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem	CoRR	2009	DBLP BibTeX RDF
1	Benjamin Doerr, Magnus Wahlström	Randomized Rounding in the Presence of a Cardinality Constraint.	ALENEX	2009	DBLP BibTeX RDF
1	V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy 0002, Aravind Srinivasan	A unified approach to scheduling on unrelated parallel machines.	J. ACM	2009	DBLP DOI BibTeX RDF	scheduling under multiple criteria, Approximation algorithms, randomized rounding
1	Xiaoxia Wu, Paul Falkenstern, Krishnendu Chakrabarty, Yuan Xie	Scan-chain design and optimization for three-dimensional integrated circuits.	JETC	2009	DBLP DOI BibTeX RDF	scan-chain design, genetic algorithm, integer linear programming, randomized rounding, LP relaxation, 3D ICs
1	Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein	On the approximability of Dodgson and Young elections.	SODA	2009	DBLP DOI BibTeX RDF
1	Julia Chuzhoy, Paolo Codenotti	Resource Minimization Job Scheduling.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh	PASS Approximation.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann	Deconstructing Intractability: A Case Study for Interval Constrained Coloring.	CPM	2009	DBLP DOI BibTeX RDF
1	Rajmohan Rajaraman	Randomized Rounding.	Encyclopedia of Algorithms	2008	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Tim Roughgarden	Metric clustering via consistent labeling.	SODA	2008	DBLP DOI BibTeX RDF
1	Matthew Andrews, Lisa Zhang	Almost-tight hardness of directed congestion minimization.	J. ACM	2008	DBLP DOI BibTeX RDF	Hardness of approximation, undirected graphs, congestion minimization
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	Xiaoxia Wu, Yibo Chen, Krishnendu Chakrabarty, Yuan Xie	Test-access mechanism optimization for core-based three-dimensional SOCs.	ICCD	2008	DBLP DOI BibTeX RDF
1	René A. Sitters	Approximability of Average Completion Time Scheduling on Unrelated Machines.	ESA	2008	DBLP DOI BibTeX RDF
1	Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko	Min Sum Edge Coloring in Multigraphs Via Configuration LP.	IPCO	2008	DBLP DOI BibTeX RDF	Edge Scheduling, Configuration LP, Approximation Algorithms
1	Leizhen Cai, Elad Verbin, Lin Yang	Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Arash Asadpour, Amin Saberi	An approximation algorithm for max-min fair allocation of indivisible goods.	STOC	2007	DBLP DOI BibTeX RDF	approximation algorithms, game theory, randomized rounding
1	Yossi Azar, Iftah Gamzu, Shai Gutner	Truthful unsplittable flow for large capacity networks.	SPAA	2007	DBLP DOI BibTeX RDF	combinatorial and multi-unit auctions, approximation algorithms, mechanism design, primal-dual method
1	Fabian Kuhn, Thomas Moscibroda	Distributed approximation of capacitated dominating sets.	SPAA	2007	DBLP DOI BibTeX RDF	distributed approximation, capacities, dominating sets, LP relaxation
1	Kalyana R. Kantipudi, Vishwani D. Agrawal	A Reduced Complexity Algorithm for Minimizing N-Detect Tests.	VLSI Design	2007	DBLP DOI BibTeX RDF
1	Vladimir V. V'yugin	On Calibration Error of Randomized Forecasting Algorithms.	ALT	2007	DBLP DOI BibTeX RDF
1	Peng Zhang, Wenbo Zhao	On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems.	ESCAPE	2007	DBLP DOI BibTeX RDF
1	Benjamin Doerr	Roundings Respecting Hard Constraints.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Christian Klein	Controlled Randomized Rounding.	Electronic Notes in Discrete Mathematics	2006	DBLP DOI BibTeX RDF
1	Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, Tomomi Matsui	Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling.	IEICE Transactions	2006	DBLP DOI BibTeX RDF
1	Benjamin Doerr	Non-independent randomized rounding and coloring.	Discrete Applied Mathematics	2006	DBLP DOI BibTeX RDF
1	Vasilis Friderikos, Katerina Papadaki, Dave Wisely, A. Hamid Aghvami	Non-Independent Randomized Rounding for Link Scheduling in Wireless Mesh Networks.	VTC Fall	2006	DBLP DOI BibTeX RDF
1	Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor	A general approach to online network optimization problems.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	Online network optimization, group Steiner, multi-cuts, competitive analysis, facility location, randomized rounding
1	Geir Dahl, Njål Foldnes	LP based heuristics for the multiple knapsack problem with assignment restrictions.	Annals OR	2006	DBLP DOI BibTeX RDF	Randomized rounding, Traffic routing, Multiple knapsack problem
1	Vikas Singh, Lopamudra Mukherjee, Jinhui Xu, Kenneth R. Hoffmann	Solving the brachytherapy seed localization problem using geometric and linear programming techniques.	SAC	2006	DBLP DOI BibTeX RDF	brachytherapy seed localization, linear programming, geometric optimization
1	Matthew Andrews, Lisa Zhang	Logarithmic hardness of the directed congestion minimization problem.	STOC	2006	DBLP DOI BibTeX RDF	directed graphs, hardness of approximation, congestion minimization
1	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
1	Nikhil Bansal, Alberto Caprara, Maxim Sviridenko	Improved approximation algorithms for multidimensional bin packing problems.	FOCS	2006	DBLP DOI BibTeX RDF
1	Allan Borodin	Further Reflections on a Theory for Basic Algorithms.	AAIM	2006	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Christian Klein	Unbiased Rounding of Rational Matrices.	FSTTCS	2006	DBLP DOI BibTeX RDF
1	Yossi Azar, Oded Regev	Combinatorial Algorithms for the Unsplittable Flow Problem.	Algorithmica	2006	DBLP DOI BibTeX RDF	Unsplittable flow problem, Combinatorial algorithms
1	Jiawei Zhang	Approximating the two-level facility location problem via a quasi-greedy approach.	Math. Program.	2006	DBLP DOI BibTeX RDF	Two-level facility location, Quasi-greedy approach, Approximation algorithm, Linear programming relaxation
1	Patrick Briest, Piotr Krysta, Berthold Vöcking	Approximation techniques for utilitarian mechanism design.	STOC	2005	DBLP DOI BibTeX RDF	combinatorial and multi-unit auctions, enumeration techniques, approximation algorithms, mechanism design, primal-dual method
1	Joseph Naor	From Balanced Graph Partitioning to Balanced Metric Labeling.	ESA	2005	DBLP DOI BibTeX RDF
1	Kedar Dhamdhere, R. Ravi, Mohit Singh	On Two-Stage Stochastic Minimum Spanning Trees.	IPCO	2005	DBLP DOI BibTeX RDF
1	Benjamin Doerr	Roundings Respecting Hard Constraints.	STACS	2005	DBLP DOI BibTeX RDF
1	Benjamin Doerr	Nonindependent Randomized Rounding and an Application to Digital Halftoning.	SIAM J. Comput.	2004	DBLP DOI BibTeX RDF
1	Minos N. Garofalakis, Phillip B. Gibbons	Probabilistic wavelet synopses.	ACM Trans. Database Syst.	2004	DBLP DOI BibTeX RDF	Wavelets, randomized rounding, approximate query processing, data synopses
1	Uriel Feige, László Lovász, Prasad Tetali	Approximating Min Sum Set Cover.	Algorithmica	2004	DBLP DOI BibTeX RDF	Threshhold, NP-hardness, Greedy algorithm, Randomized rounding
1	Hanson Zhou, David P. Woodruff	Clustering via Matrix Powering. (PDF / PS)	PODS	2004	DBLP DOI BibTeX RDF
1	Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos	Approximate classification via earthmover metrics.	SODA	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	Jiawei Zhang	Approximating the two-level facility location problem via a quasi-greedy approach.	SODA	2004	DBLP DOI BibTeX RDF
1	Yi Cui, Baochun Li, Klara Nahrstedt	On achieving optimized capacity utilization in application overlay networks with multiple competing sessions.	SPAA	2004	DBLP DOI BibTeX RDF	multicast, overlay, multicommodity flow
1	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
1	Sobeeh Almukhaizim, Petros Drineas, Yiorgos Makris	On Concurrent Error Detection with Bounded Latency in FSMs.	DATE	2004	DBLP DOI BibTeX RDF
1	Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor	Machine Minimization for Scheduling Jobs with Interval Constraints.	FOCS	2004	DBLP DOI BibTeX RDF
1	Liu Hongwei, Wang Xinhui, Liu Sanyang	The application of nonlinear programming for multiuser detection in CDMA.	IEEE Transactions on Wireless Communications	2004	DBLP DOI BibTeX RDF
1	Piotr Berman, Bhaskar DasGupta, Eduardo D. Sontag	Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Maren Martens, Martin Skutella	Flows on Few Paths: Algorithms and Lower Bounds.	ESA	2004	DBLP DOI BibTeX RDF
1	Jens Vygen	Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption.	IPCO	2004	DBLP DOI BibTeX RDF
1	Ioannis Caragiannis, Christos Kaklamanis	Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks.	STACS	2004	DBLP DOI BibTeX RDF
1	Carlos A. J. Martinhon, Fábio Protti	An Improved Derandomized Approximation Algorithm for the Max-Controlled Set Problem.	WEA	2004	DBLP DOI BibTeX RDF
1	Carla P. Gomes, David B. Shmoys	Approximations and Randomization to Boost CSP Techniques.	Annals OR	2004	DBLP DOI BibTeX RDF
1	Benjamin Doerr	Non-independent randomized rounding.	SODA	2003	DBLP DOI BibTeX RDF
1	Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor	The online set cover problem.	STOC	2003	DBLP DOI BibTeX RDF	competitive analysis, on-line algorithms, set-cover, derandomization, randomized rounding
1	Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos	An approximate truthful mechanism for combinatorial auctions with single parameter agents.	SODA	2003	DBLP DOI BibTeX RDF
1	Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram	Meet and merge: approximation algorithms for confluent flows.	STOC	2003	DBLP DOI BibTeX RDF	confluent flow, routing, approximation algorithms, randomization, network flow, multicommodity flow, rounding
1	Martin E. Dyer	Approximate counting by dynamic programming.	STOC	2003	DBLP DOI BibTeX RDF
1	Petros Drineas, Yiorgos Makris	Independent Test Sequence Compaction through Integer Programming.	ICCD	2003	DBLP DOI BibTeX RDF
1	Thomas Hofmeister	An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint.	ESA	2003	DBLP DOI BibTeX RDF
1	Martin Hoefer	Experimental Comparison of Heuristic and Approximation Algorithms for Uncapacitated Facility Location.	WEA	2003	DBLP DOI BibTeX RDF
1	Neal E. Young	Randomized Rounding without Solving the Linear Program	CoRR	2002	DBLP BibTeX RDF
1	Andreas S. Schulz, Martin Skutella	Scheduling Unrelated Machines by Randomized Rounding.	SIAM J. Discrete Math.	2002	DBLP DOI BibTeX RDF
1	Anupam Datta, Sidharth Choudhury, Anupam Basu	Using Randomized Rounding to Satisfy Timing Constraints of Real-Time Preemptive Tasks.	VLSI Design	2002	DBLP DOI BibTeX RDF
1	D. Sivakumar	Algorithmic derandomization via complexity theory.	STOC	2002	DBLP DOI BibTeX RDF
1	Julia Chuzhoy, Joseph Naor	Covering Problems with Hard Capacities.	FOCS	2002	DBLP DOI BibTeX RDF
1	Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy 0002, Aravind Srinivasan	Dependent Rounding in Bipartite Graphs.	FOCS	2002	DBLP DOI BibTeX RDF
1	Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar	Approximation Algorithms for the Unsplittable Flow Problem.	APPROX	2002	DBLP DOI BibTeX RDF
1	Uriel Feige, Michael Langberg	The RPR2 Rounding Technique for Semidefinite Programs.	ICALP	2001	DBLP DOI BibTeX RDF
1	V. Kumar	An Approximation Algorithm for Circular Arc Colouring.	Algorithmica	2001	DBLP DOI BibTeX RDF