Search results for "k-median"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Shai Ben-David	A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering.	Machine Learning	2007	DBLP DOI BibTeX RDF	k-median clustering, Sample-based clustering, Description schemes, Approximation algorithms, k-means clustering
3	Sariel Har-Peled, Soham Mazumdar	On coresets for k-means and k-median clustering.	STOC	2004	DBLP DOI BibTeX RDF	clustering, streaming, k-means, k-median, Coreset
3	Kamal Jain, Vijay V. Vazirani	Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation.	J. ACM	2001	DBLP DOI BibTeX RDF	approximation algorithms, linear programming, Lagrangian relaxation, facility location problem, k-median problem
3	Kamal Jain, Vijay V. Vazirani	Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems.	FOCS	1999	DBLP DOI BibTeX RDF	approximation algorithms, linear programming, facility location, k-median
3	Moses Charikar, Sudipto Guha	Improved Combinatorial Algorithms for the Facility Location and k-Median Problems.	FOCS	1999	DBLP DOI BibTeX RDF	linear programming, approximation, local search, facility location, combinatorial algorithms, k-median
2	Ke Chen 0006	A constant factor approximation algorithm for k-median clustering with outliers.	SODA	2008	DBLP DOI BibTeX RDF
2	DongMei Xing	Nonmetric Multicommodity Facility Location and K-Median Problem with Service Installation Costs.	CSSE	2008	DBLP DOI BibTeX RDF
2	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
2	Sariel Har-Peled, Akash Kushal	Smaller Coresets for k-Median and k-Means Clustering.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF
2	Sven de Vries, Marc E. Posner, Rakesh V. Vohra	Polyhedral Properties of the K -median Problem on a Tree.	Math. Program.	2007	DBLP DOI BibTeX RDF	Polyhedral description, Lifting, Facets, Valid inequalities
2	Amit Kumar, Yogish Sabharwal	The Priority k-Median Problem.	FSTTCS	2007	DBLP DOI BibTeX RDF
2	Ke Chen 0006	On k-Median clustering in high dimensions.	SODA	2006	DBLP DOI BibTeX RDF
2	Julia Chuzhoy, Yuval Rabani	Approximating k-median with non-uniform capacities.	SODA	2005	DBLP DOI BibTeX RDF
2	Sariel Har-Peled, Akash Kushal	Smaller coresets for k-median and k-means clustering.	Symposium on Computational Geometry	2005	DBLP DOI BibTeX RDF	clustering, coresets
2	Marek Chrobak, Claire Kenyon, Neal E. Young	The Reverse Greedy Algorithm for the Metric K-Median Problem.	COCOON	2005	DBLP DOI BibTeX RDF	approximation algorithms, online algorithms, Analysis of algorithms
2	Adam Meyerson, Liadan O'Callaghan, Serge A. Plotkin	A k-Median Algorithm with Running Time Independent of Data Size.	Machine Learning	2004	DBLP DOI BibTeX RDF	sublinear, clustering, sampling
2	Dimitris Fotakis	Incremental Algorithms for Facility Location and k-Median.	ESA	2004	DBLP DOI BibTeX RDF
2	Shai Ben-David	A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering.	COLT	2004	DBLP DOI BibTeX RDF
2	Ramgopal R. Mettu, C. Greg Plaxton	Optimal Time Bounds for Approximate Clustering.	Machine Learning	2004	DBLP DOI BibTeX RDF	discrete location theory, approximation algorithms, k-means, unsupervised clustering, k-median
2	Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys	Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties.	ESA	2003	DBLP DOI BibTeX RDF
2	Moses Charikar, Liadan O'Callaghan, Rina Panigrahy	Better streaming algorithms for clustering problems.	STOC	2003	DBLP DOI BibTeX RDF	clustering, streaming algorithm, k-median
2	Eva Gómez-Ballester, Luisa Micó, José Oncina	A Fast Approximated k-Median Algorithm.	SSPR/SPR	2002	DBLP DOI BibTeX RDF
2	Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter	The k-Median Problem for Directed Trees.	MFCS	2001	DBLP DOI BibTeX RDF
2	Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit	Local search heuristic for k-median and facility location problems.	STOC	2001	DBLP DOI BibTeX RDF
2	John D. Kececioglu, Jun Ju	Separtating repeats in DNA sequence assembly.	RECOMB	2001	DBLP DOI BibTeX RDF	disambiguating repeats, shotgun sequencing, computational biology, k-median problem
1	Piotr Indyk, Eric Price	K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance	CoRR	2011	DBLP BibTeX RDF
1	Wenhui Zhao, Marc E. Posner	A large class of facets for the K-median polytope.	Math. Program.	2011	DBLP DOI BibTeX RDF
1	Chandrashekhar Nagarajan, David P. Williamson	An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms.	SEA	2011	DBLP DOI BibTeX RDF
1	Piotr Indyk, Eric Price	K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.	STOC	2011	DBLP DOI BibTeX RDF
1	Zhihong Chong, Weiwei Ni, Lizhen Xu, Zhuoming Xu, Hu Shu, Jinwang Zheng	Approximate K-Median of Location Streams with Redundancy and Inconsistency.	Int. J. Software and Informatics	2010	DBLP BibTeX RDF
1	Parneeta Dhaliwal, M. P. S. Bhatia, Priti Bansal	A Cluster-based Approach for Outlier Detection in Dynamic Data Streams (KORM: k-median OutlieR Miner)	CoRR	2010	DBLP BibTeX RDF
1	Pranjal Awasthi, Avrim Blum, Or Sheffet	Stability Yields a PTAS for k-Median and k-Means Clustering.	FOCS	2010	DBLP DOI BibTeX RDF
1	Guy E. Blelloch, Kanat Tangwongsan	Parallel approximation algorithms for facility-location problems.	SPAA	2010	DBLP DOI BibTeX RDF	parallel algorithms, approximation algorithms, facility location problems
1	Anureet Saxena, Vineet Goyal, Miguel A. Lejeune	MIP reformulations of the probabilistic set covering problem.	Math. Program.	2010	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C15, 90-08, 90C10
1	Marcel R. Ackermann	Algorithms for the Bregman k-Median problem.		2009	RDF
1	Ke Chen 0006	On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications.	SIAM J. Comput.	2009	DBLP DOI BibTeX RDF
1	Yoonheui Kim, Victor R. Lesser, Deepak Ganesan, Ramesh K. Sitaraman	Cluster-Swap: A Distributed K-median Algorithm for Sensor Networks.	IAT	2009	DBLP DOI BibTeX RDF
1	Marcel R. Ackermann, Johannes Blömer	Coresets and approximate clustering for Bregman divergences.	SODA	2009	DBLP DOI BibTeX RDF
1	Maria-Florina Balcan, Avrim Blum, Anupam Gupta	Approximate clustering without the approximation.	SODA	2009	DBLP DOI BibTeX RDF
1	Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim	Private coresets.	STOC	2009	DBLP DOI BibTeX RDF	privacy, differential privacy, coresets
1	Adam Meyerson, Brian Tagiku	Minimizing Average Shortest Path Distances via Shortcut Edge Addition.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Graham Cormode, Andrew McGregor	Approximation algorithms for clustering uncertain data.	PODS	2008	DBLP DOI BibTeX RDF	clustering, probabilistic data
1	Marcel R. Ackermann, Johannes Blömer, Christian Sohler	Clustering for metric and non-metric distance measures.	SODA	2008	DBLP DOI BibTeX RDF
1	Barbara M. Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan	A plant location guide for the unsure.	SODA	2008	DBLP DOI BibTeX RDF
1	Julien Gossa, Nipaul Long	Multi-ressources K-Médians: un algorithme de placement de services web sur les réseaux sans fils municipaux.	UbiMob	2008	DBLP DOI BibTeX RDF	deployment plan, web services, placement, k-medians
1	Zachary Friggstad, Mohammad R. Salavatipour	Minimizing Movement in Mobile Facility Location Problems.	FOCS	2008	DBLP DOI BibTeX RDF
1	Qi Zhang, Jinze Liu, Wei Wang 0010	Approximate Clustering on Distributed Data Streams.	ICDE	2008	DBLP DOI BibTeX RDF
1	Joshua Robinson, Mustafa Uysal, Ram Swaminathan, Edward W. Knightly	Adding Capacity Points to a Wireless Mesh Network Using Local Search.	INFOCOM	2008	DBLP DOI BibTeX RDF
1	Abhimanyu Das, David Kempe	Sensor Selection for Minimizing Worst-Case Prediction Error.	IPSN	2008	DBLP DOI BibTeX RDF	estimation, spatial correlation, sensor selection, sensor placement
1	Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young	Incremental Medians via Online Bidding.	Algorithmica	2008	DBLP DOI BibTeX RDF
1	Stavros G. Kolliopoulos, Satish Rao	A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem.	SIAM J. Comput.	2007	DBLP DOI BibTeX RDF
1	Aiyesha Ma, Ishwar K. Sethi	Distributed K-Median Clustering with Application to Image Clustering.	PRIS	2007	DBLP BibTeX RDF
1	Dan Feldman, Amos Fiat, Micha Sharir, Danny Segev	Bi-criteria linear-time approximations for generalized k-mean/median/center.	Symposium on Computational Geometry	2007	DBLP DOI BibTeX RDF	bi-criteria approximation, approximation, k-mean, geometric optimization, k-median, k-center
1	Rajgopal Kannan, Shuangqing Wei, Vasu Chakravarthy, Murali Rangaswamy	A Fully Polynomial Approximation Algorithm for Collaborative Relaying in Sensor Networks Under Finite Rate Constraints.	DCOSS	2007	DBLP DOI BibTeX RDF
1	Saara Hyvönen, Aristides Gionis, Heikki Mannila	Recurrent Predictive Models for Sequence Segmentation.	IDA	2007	DBLP DOI BibTeX RDF
1	Amos Beimel, Renen Hallak, Kobbi Nissim	Private Approximation of Clustering and Vertex Cover.	TCC	2007	DBLP DOI BibTeX RDF
1	Marek Chrobak, Mathilde Hurand	Better Bounds for Incremental Medians.	WAOA	2007	DBLP DOI BibTeX RDF	Incremental medians, approximation algorithm, online algorithm, analysis of algorithms
1	Marek Chrobak, Claire Kenyon, Neal E. Young	The reverse greedy algorithm for the metric k-median problem.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
1	Dimitris Fotakis	Incremental algorithms for Facility Location and k-Median.	Theor. Comput. Sci.	2006	DBLP DOI BibTeX RDF
1	Amal Perera, William Perrizo	Vertical K-Median Clustering.	Computers and Their Applications	2006	DBLP BibTeX RDF
1	Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu	Self-improving algorithms.	SODA	2006	DBLP DOI BibTeX RDF
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	Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson	A general approach for incremental approximation and hierarchical clustering.	SODA	2006	DBLP DOI BibTeX RDF
1	Dan Feldman, Amos Fiat, Micha Sharir	Coresets forWeighted Facilities and Their Applications.	FOCS	2006	DBLP DOI BibTeX RDF
1	Zengyou He, Shengchun Deng, Xiaofei Xu	Approximation Algorithms for K-Modes Clustering.	ICIC	2006	DBLP DOI BibTeX RDF
1	Peng Zhang	A New Approximation Algorithm for the k-Facility Location Problem.	TAMC	2006	DBLP DOI BibTeX RDF
1	Marek Chrobak, Claire Kenyon, Neal E. Young	The reverse greedy algorithm for the metric k-median problem	CoRR	2005	DBLP BibTeX RDF
1	Amit Kumar, Yogish Sabharwal, Sandeep Sen	Linear Time Algorithms for Clustering Problems in Any Dimensions.	ICALP	2005	DBLP DOI BibTeX RDF
1	Mingjun Song, Sanguthevar Rajasekaran	Fast k-Means Algorithms with Constant Approximation.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit	Local Search Heuristics for k-Median and Facility Location Problems.	SIAM J. Comput.	2004	DBLP DOI BibTeX RDF
1	Mikkel Thorup	Quick k-Median, k-Center, and Facility Location for Sparse Graphs.	SIAM J. Comput.	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	Kunal Talwar	Bypassing the embedding: algorithms for low dimensional metrics.	STOC	2004	DBLP DOI BibTeX RDF	TSP, PTAS, routing schemes, doubling metrics, distance labels
1	Wei Wei, King Ngi Ngan	Integration of motion and image features for automatic video object segmentation.	ICIP	2004	DBLP DOI BibTeX RDF
1	Artur Czumaj, Christian Sohler	Sublinear-Time Approximation for Clustering Via Random Sampling.	ICALP	2004	DBLP DOI BibTeX RDF
1	Chaitanya Swamy, Amit Kumar	Primal-Dual Algorithms for Connected Facility Location Problems.	Algorithmica	2004	DBLP DOI BibTeX RDF	Approximation algorithms, Steiner trees, Facility location, Primal-dual algorithms, Connected facility location
1	Nikhil Bansal, Avrim Blum, Shuchi Chawla	Correlation Clustering.	Machine Learning	2004	DBLP DOI BibTeX RDF	clustering, approximation algorithm, document classification
1	Fabián A. Chudak, Tim Roughgarden, David P. Williamson	Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation.	Math. Program.	2004	DBLP DOI BibTeX RDF
1	Brian Babcock, Mayur Datar, Rajeev Motwani, Liadan O'Callaghan	Maintaining variance and k-medians over data stream windows.	PODS	2003	DBLP DOI BibTeX RDF
1	C. Greg Plaxton	Approximation algorithms for hierarchical location problems.	STOC	2003	DBLP DOI BibTeX RDF	discrete location theory, hierarchical clustering
1	Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani	Approximation schemes for clustering problems.	STOC	2003	DBLP DOI BibTeX RDF
1	Robert Benkoczi, Binay K. Bhattacharya, Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter	Faster Algorithms for k-Medians in Trees.	MFCS	2003	DBLP DOI BibTeX RDF
1	Inge Li Gørtz, Anthony Wirth	Asymmetry in k-Center Variants.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
1	Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys	A Constant-Factor Approximation Algorithm for the k-Median Problem.	J. Comput. Syst. Sci.	2002	DBLP DOI BibTeX RDF
1	Mihai Badoiu, Sariel Har-Peled, Piotr Indyk	Approximate clustering via core-sets.	STOC	2002	DBLP DOI BibTeX RDF
1	Kamal Jain, Mohammad Mahdian, Amin Saberi	A new greedy approach for facility location problems.	STOC	2002	DBLP DOI BibTeX RDF
1	Rafail Ostrovsky, Yuval Rabani	Polynomial-time approximation schemes for geometric min-sum median clustering.	J. ACM	2002	DBLP DOI BibTeX RDF	Clustering, high-dimensional data, polynomial-time approximation schemes
1	Nikhil Bansal, Avrim Blum, Shuchi Chawla	Correlation Clustering.	FOCS	2002	DBLP DOI BibTeX RDF
1	Adrian Vetta	Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions.	FOCS	2002	DBLP DOI BibTeX RDF
1	Chaitanya Swamy, Amit Kumar	Primal-Dual Algorithms for Connected Facility Location Problems.	APPROX	2002	DBLP DOI BibTeX RDF
1	Mikkel Thorup	Quick k-Median, k-Center, and Facility Location for Sparse Graphs.	ICALP	2001	DBLP DOI BibTeX RDF
1	Fabián A. Chudak, Tim Roughgarden, David P. Williamson	Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation.	IPCO	2001	DBLP DOI BibTeX RDF
1	Antoine Vigneron, Lixin Gao, Mordecai J. Golin, Giuseppe F. Italiano, Bo Li	An algorithm for finding a k-median in a directed tree.	Inf. Process. Lett.	2000	DBLP DOI BibTeX RDF
1	Sándor P. Fekete, Joseph S. B. Mitchell, Karin Weinbrecht	On the continuous Weber and k-median problems (extended abstract).	Symposium on Computational Geometry	2000	DBLP DOI BibTeX RDF
1	Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan	Clustering Data Streams.	FOCS	2000	DBLP DOI BibTeX RDF	data stream clustering, point sequence, data stream model, Web click stream analysis, multimedia data analysis, constant-factor approximation algorithms, computational complexity, data analysis, deterministic algorithms, deterministic algorithms, very large databases, massive data sets, pattern clustering, k-median problem
1	Ramgopal R. Mettu, C. Greg Plaxton	The Online Median Problem.	FOCS	2000	DBLP DOI BibTeX RDF	online median problem, linear-time constant-competitive algorithm, linear-time constant-factor approximation algorithm, primal-dual-based facility location algorithm, facility location, heuristic programming, competitive ratio, approximation theory, k-median problem, worst-case ratio
1	Rafail Ostrovsky, Yuval Rabani	Polynomial Time Approximation Schemes for Geometric k-Clustering.	FOCS	2000	DBLP DOI BibTeX RDF	geometric k-clustering, data point clustering, data set partitioning, high dimensional geometry, binary cube, computational complexity, computational geometry, Hamming distance, NP-hard problem, distance function, polynomial time approximation schemes, pattern clustering, k-median problem
1	David B. Shmoys	Approximation algorithms for facility location problems.	APPROX	2000	DBLP DOI BibTeX RDF
1	Dominique Peeters, Isabelle Thomas	Distance predicting functions and applied location-allocation models..	Journal of Geographical Systems	2000	DBLP DOI BibTeX RDF
1	Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys	A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract).	STOC	1999	DBLP DOI BibTeX RDF