Publications (dblp, Google Scholar)
The versions you can download here do not necessarily coincide with the original publications, which can be found by following the links.
[C51] |
Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering
To appear in Proc. of the 38th NeurIPS, 2024.
|
|
[C50] |
On the number of iterations of the DBA algorithm
In Proc. of the 24th SDM, pp. 172–180, 2024.
|
|
[C49] |
Connected k-Center and k-Diameter Clustering
In Proc. of the 50th ICALP, pp. 50:1-50:20, 2023.
Also appeared in Algorithmica (see [J33]).
|
|
[C48] |
The Price of Hierarchical Clustering
In Proc. of the 30th ESA, pp. 10:1-10:14, 2022.
|
|
[C47] |
Minimum-Error Triangulations for Sea Surface Reconstruction
In Proc. of the 38th SoCG, pp. 7:1-7:18, 2022.
Also appeared in Journal of Computational Geometry (see [J31]).
|
|
[C46] |
Upper and Lower Bounds for Complete Linkage in General Metric Spaces
In Proc. of the 24th Approx, pp. 18:1-18:22, 2021.
Also appeared in Machine Learning (see [J32]).
|
|
[C45] |
Bicriteria Aggregation of Polygons via Graph Cuts
In Proc. of the 11th GIScience, pp. 6:1-6:16,2021.
Also to appear in ACM Transactions on Spatial Algorithms and Systems (see [J34]).
|
|
[C44] |
Noisy, Greedy and Not So Greedy k-means++
In Proc. of the 28th ESA (Pisa, Italy), pp. 18:1-18:21, 2020.
|
|
[C43] |
Analysis of Ward's Method
In Proc. of the 30th SODA (San Diego, USA), pp. 2939-2957, 2019.
|
|
[C42] |
Probabilistic Analysis of (Class-constrained) Bin Packing and Bin Covering
In Proc. of the 13th LATIN (Buenos Aires, Argentina), pp. 461-474, 2018.
|
|
[C41] |
The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization
In Proc. of the 14th TAMC (Bern, Switzerland), pp. 543-555, 2017.
Also appeared in Mathematical Programming (see [J30]).
|
|
[C40] |
Bounds for the Convergence Time of Local Search in Scheduling Problems
In Proc. of the 12th WINE (Montreal, Canada), pp. 339-353, 2016.
|
|
[C39] |
The Alternating Stock Size Problem and the Gasoline Puzzle
In Proc. of the 24th ESA (Aarhus, Denmark), pp. 71:1-71:16, 2016.
Also appeared in ACM Transactions on Algorithms (see [J28]).
|
|
[C38] |
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 469-482, 2016.
|
|
[C37] |
New Deterministic Algorithms for Solving Parity Games
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 634-645, 2016.
Also appeared in Discrete Optimization (see [J29]).
|
|
[C36] |
Improved Analysis of Complete-Linkage Clustering
In Proc. of the 23rd ESA (Patras, Greece), pp. 656-667, 2015.
Also appeared in special issue of Algorithmica (see [J27]).
|
|
[C35] |
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
In Proc. of the 23rd ESA (Patras, Greece), pp. 509-520, 2015.
|
|
[C34] |
Polynomial Kernels for Weighted Problems
In Proc. of the 40th MFCS (Milano, Italy), pp. 287-298, 2015.
Also appeared in Journal of Computer and System Sciences (see [J25]).
|
|
[C33] |
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
In Proc. of the 32nd STACS (Munich, Germany), pp. 171-183, 2015.
|
|
[C32] |
Smoothed Analysis of Local Search for the Maximum-Cut Problem
In Proc. of the 25th SODA (Portland, USA), pp. 882-889, 2014.
|
|
[C31] |
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
In Proc. of the 40th ICALP (Riga, Latvia), pp. 279-290, 2013.
|
|
[C30] |
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
In Proc. of the 7th WALCOM (Kharagpur, India), pp. 182-193, 2013.
Also appeared in special issue of Journal of Graph Algorithms and Applications (see [J17]).
|
|
[C29] |
Smoothed Analysis of the Successive Shortest Path Algorithm
In Proc. of the 24th SODA (New Orleans, USA), pp. 1180-1189, 2013.
Also appeared in SIAM Journal on Computing (see [J23]).
|
|
[C28] |
Improved Smoothed Analysis of Multiobjective Optimization
In Proc. of the 44th STOC (New York, USA), pp. 407-426, 2012.
Also appeared in Journal of the ACM (see [J21]).
|
|
[C27] |
Smoothed Performance Guarantees for Local Search
In Proc. of the 19th ESA (Saarbrücken, Germany), pp. 772-783, 2011.
Also appeared in Mathematical Programming (see [J18]).
|
|
[C26] |
Min-Sum Clustering of Protein Sequences with Limited Distance Information
In Proc. of the 1st SIMBAD (Venice, Italy), pp. 192-206, 2011.
|
|
[C25] |
Lower Bounds for the Smoothed Number of Pareto optimal Solutions
In Proc. of the 8th TAMC (Tokyo, Japan), pp. 416-427, 2011.
Also appeared in Theory of Computing (see [J20]).
|
|
[C24] |
A Bad Instance for k-means++
In Proc. of the 8th TAMC (Tokyo, Japan), pp. 344-352, 2011.
Also appeared in special issue of Theoretical Computer Science (see [J14]).
|
|
[C23] |
Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results
In Proc. of the 10th SEA (Crete, Greece), pp. 43-53, 2011.
Also appeared in Discrete Applied Mathematics (see [J22]).
|
|
[C22] |
The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers
In Proc. of the 8th WAOA (Liverpool, U.K.), pp. 47-58, 2010.
|
|
[C21] |
Efficient Clustering with Limited Distance Information
In Proc. of the 26th UAI (Catalina Island, USA), pp. 632-641, 2010.
Also appeared in Journal of Machine Learning Research (see [J13]).
|
|
[C20] |
Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem
In Proc. of the 7th ANTS (Brussels, Belgium), pp. 324-335, 2010.
Also appeared in Swarm Intelligence (see [J12]).
Best Paper Award of ANTS 2010
|
|
[C19] |
Competitive Routing over Time
In Proc. of the 5th WINE (Rome, Italy), pp. 18-29, 2009.
Also appeared in Theoretical Computer Science (see [J9]).
|
|
[C18] |
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
In Proc. of the 20th ISAAC (Hawaii, USA), pp. 1024-1033, 2009.
Also appeared in Journal of Computational Geometry (see [J16]).
|
|
[C17] |
Smoothed Analysis of Multiobjective Optimization
In Proc. of the 50th FOCS (Atlanta, USA), pp. 681-690, 2009.
|
|
[C16] |
k-Means has Polynomial Smoothed Complexity
In Proc. of the 50th FOCS (Atlanta, USA), pp. 405-414, 2009.
Also appeared in Journal of the ACM (see [J8]).
|
|
[C15] |
Agnostic Clustering
In Proc. of the 20th ALT (Porto, Portugal), pp. 384-398, 2009.
|
|
[C14] |
Economical Caching
In Proc. of the 26th STACS (Freiburg, Germany), pp. 385-396, 2009.
Also appeared in ACM Transactions on Computation Theory (see [J15]).
|
|
[C13] |
Improved Smoothed Analysis of the k-Means Method
In Proc. of the 20th SODA (New York, USA), pp. 461-470, 2009.
|
|
[C12] |
Uncoordinated Two-Sided Matching Markets
In Proc. of the 9th EC (Chicago, USA), pp. 256-263, 2008.
Also appeared in SIAM Journal on Computing (see [J7]).
Outstanding Paper Award of EC 2008
|
|
[C11] |
Computing Approximate Nash Equilibria in Network Congestion Games
In Proc. of the 15th SIROCCO (Villars-sur-Ollon, Switzerland), pp. 209-220, 2008.
Also appeared in Networks (see [J11]).
|
|
[C10] |
A Unified Approach to Congestion Games and Two-Sided Markets
In Proc. of the 3rd WINE (San Diego, USA), pp. 30-41, 2007.
Also appeared in special issue of Internet Mathematics (see [J4]).
|
|
[C9] |
The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
In Proc. of the 12th IPCO (Ithaca, USA), pp. 53-67, 2007.
Also appeared in Mathematical Programming (see [J30]).
|
|
[C8] |
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
In Proc. of the 18th SODA (New Orleans, USA), pp. 1295-1304, 2007.
Also appeared in parts in Algorithmica (see [J19]).
Also appeared in parts in ACM Transactions on Algorithms (see [J24]).
|
|
[C7] |
Pure Nash Equilibria in Player-Specific and Weighted Congestion Games
In Proc. of the 2nd WINE (Patras, Greece), pp. 50-61, 2006.
Also appeared in special issue of Theoretical Computer Science (see [J5]).
|
|
[C6] |
On the Impact of Combinatorial Structure on Congestion Games
In Proc. of the 47th FOCS (Berkeley, USA), pp. 613-622, 2006.
Also appeared in Journal of the ACM (see [J3]).
|
|
[C5] |
Evaluation of Online Strategies for Reordering Buffers
In Proc. of the 5th WEA (Menorca Island, Spain), pp. 183-194, 2006.
Also appeared in special issue of ACM Journal of Experimental Algorithmics (see [J6]).
|
|
[C4] |
Decision Making Based on Approximate and Smoothed Pareto Curves
In Proc. of the 16th ISAAC (Sanya, China), pp. 675-684, 2005.
Also appeared in special issue of Theoretical Computer Science (see [J2]).
|
|
[C3] |
Smoothed Analysis of Integer Programming
In Proc. of the 11th IPCO (Berlin, Germany), pp. 276-290, 2005.
Also appeared in special issue of Mathematical Programming (see [J1]).
|
|
[C2] |
The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
In Proc. of the 8th PPSN (Birmingham, UK), pp. 31-40, 2004.
|
|
[C1] |
Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization
In Proc. of the 8th PPSN (Birmingham, UK), pp. 21-30, 2004.
|
[TR2] |
On the Convergence Time of the Best Response Dynamics in Player-specific Congestion Games
CoRR, May 2008.
|
|
[TR1] |
Approximate Equilibria in Games with Few Players
CoRR, April 2008.
|