Page 1 of 60Free preview · 1–5

About this document

A research presentation on the worst-case running time of Lloyd’s k-means method. It reviews clustering objectives and prior complexity bounds, develops a super-polynomial lower-bound construction using signaling and reset mechanisms, and presents smoothed upper bounds through potential-function analysis. It concludes with limitations of the bounds and open questions about dimension, cluster count, and practical performance.

Free preview text

The first 5 pages, shown as text so search engines and readers can find this document.

Page 1

On the Worst-Case Complexity of the k-Means Method Sergei Vassilvitskii David Arthur (Stanford University)

Page 2

Given points in split them into similar groups. Clustering 2Rdnk

Page 3

Clustering Objectives k-Center: 3 Let be the closest cluster center to .C(x)min max x∈X ‖x − C(x)‖x

Page 4

Clustering Objectives k-Median: 4 Let be the closest cluster center to .C(x)xmin ∑ x∈X ‖x − C(x)‖

Page 5

Clustering Objectives k-Median Squared: 5 Let be the closest cluster center to .C(x)xmin ∑ x∈X ‖x − C(x)‖2 Much more sensitive to outliers

Tags

Doxxly editorial guide

On the Worst-Case Complexity of the k-Means Method: summary, contents and background

This guide helps you understand the scope of On the Worst-Case Complexity of the k-Means Method before or alongside reading the original document. It is based on the catalogue record, credited creator, source, classification and topics shown on this page. It does not replace the original work and does not invent claims about passages that Doxxly cannot verify.

Summary and overview

On the Worst-Case Complexity of the k-Means Method is a 60-page documentcredited to Xenia V. Yarrow. A research presentation on the worst-case running time of Lloyd’s k-means method. It reviews clustering objectives and prior complexity bounds, develops a super-polynomial lower-bound construction using signaling and reset mechanisms, and presents smoothed upper bounds through potential-function analysis. It concludes with limitations of the bounds and open questions about dimension, cluster count, and practical performance. It appears in the Science & Engineering collection, which groups it with other material that readers may use for comparison and further study.

The item can be approached in several ways. A reader looking for a quick orientation can begin with the free five-page preview, inspect the page structure and use the metadata to judge relevance. Someone undertaking deeper research can work through the complete file, search its indexed text, record useful page references and compare its treatment of k-means, Clustering, Lloyd’s method, Computational complexity, Worst-case analysis, Smoothed analysis, Lower bounds, Upper bounds with the related resources linked below.

Rather than reducing the work to a single claim, this page treats it as a source that should be read in context. The title, creator, publication source, licence and format all help explain what kind of evidence it may offer. Readers should distinguish the original author's statements from Doxxly's catalogue description, and should cite the original edition when using the material in academic, professional or published work.

Key topics and reader takeaways

The catalogue connects this document with k-means, Clustering, Lloyd’s method, Computational complexity, Worst-case analysis, Smoothed analysis, Lower bounds, Upper bounds. These terms offer practical entry points rather than a substitute for close reading. Start by identifying the definitions, examples, arguments, tables or visual explanations attached to each topic. Then note where the creator draws connections, makes distinctions or moves from background material to a conclusion, recommendation, calculation or narrative development.

A useful reading method is to separate description from interpretation. First record what the item actually presents: names, headings, figures, formulas, quotations or stated propositions. Next consider why those details matter within the whole work. Finally compare them with another source from the same subject area. This process helps turn a long digital file into evidence that can be evaluated rather than merely skimmed.

Table of contents and reading guide

The following is an editorial content guide based on the verified catalogue topics. It is not represented as the original author's formal table of contents. Use it to organise notes while moving through the 60 pages in the player.

  1. Part 1

    k-means

    Use this section of the reading guide to identify how k-means appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  2. Part 2

    Clustering

    Use this section of the reading guide to identify how Clustering appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  3. Part 3

    Lloyd’s method

    Use this section of the reading guide to identify how Lloyd’s method appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  4. Part 4

    Computational complexity

    Use this section of the reading guide to identify how Computational complexity appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  5. Part 5

    Worst-case analysis

    Use this section of the reading guide to identify how Worst-case analysis appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  6. Part 6

    Smoothed analysis

    Use this section of the reading guide to identify how Smoothed analysis appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  7. Part 7

    Lower bounds

    Use this section of the reading guide to identify how Lower bounds appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

  8. Part 8

    Upper bounds

    Use this section of the reading guide to identify how Upper bounds appears in On the Worst-Case Complexity of the k-Means Method, note important terms, and connect the subject to the wider purpose of the work.

When a heading in the original differs from this guide, follow the original heading in your citation. Page numbers can also vary between editions. Doxxly's direct page field is useful for navigation, but formal references should include the title, creator, source and edition details available in the file itself.

About Xenia V. Yarrow

Doxxly credits Xenia V. Yarrow as the author or creator of On the Worst-Case Complexity of the k-Means Method. This page does not add an unverified biography, job title or institutional affiliation. The attribution is preserved so readers can distinguish the creator from the hosting library and follow the original record when an external author link is available.

Author context matters because a work reflects a particular purpose, audience and point of view. Before relying on the material, consider what the creator set out to explain, when the source was produced and whether later research or revised guidance should also be consulted. For literature and philosophy, compare translations and editions; for technical material, check whether a newer version has superseded the one shown here.

About the source organisation

The recorded source for this item is theory.stanford.edu. Doxxly provides access and discovery tools but does not claim to be the original publisher unless explicitly stated. Source links, creator attribution and the recorded Publicly available file collected for editorial review licence are displayed to help readers assess provenance and permitted use.

Provenance is especially important for reports, standards, presentations and working spreadsheets. Check the original source for amendments, supporting files and current policy. A trustworthy research workflow keeps the source URL with any notes or downloaded copy, verifies important figures against the original, and avoids treating an archived document as automatically current.

Visit theory.stanford.edu

How to read and use this document

Begin with the title and opening pages, then use the guide above to decide whether to read sequentially or move to a particular topic. The Doxxly player provides previous and next navigation, a direct page field, zoom steps, fit-to-width and fit-to-page modes, rotation and fullscreen. These controls are useful when a page contains small type, a wide table, an image, a scanned layout or a dense sequence of notes.

The first five pages are open to every visitor. A plan unlocks the complete item and full-document search. Search is best used for distinctive names, technical terms or short phrases; broad words can produce too many possible contexts. When you find a useful passage, read the surrounding pages so that a sentence, chart or formula is not separated from its explanation.

If downloading is enabled, members can obtain the original PDF file. Keep the original format when formulas, slide sequencing, pagination or layout carries meaning. Respect the Publicly available file collected for editorial review terms displayed on this page, and use the rights-report link if you believe the attribution or availability needs review.

Research questions to consider

As you read On the Worst-Case Complexity of the k-Means Method, ask which audience the creator addresses, what problem or idea organises the work, what evidence is presented, and which assumptions remain unstated. Note whether important terms are defined consistently and whether examples represent a broader pattern or a narrow case. For quantitative material, record units, time periods, formulas and data sources. For interpretive material, separate the creator's language from your own summary.

A second set of questions concerns relevance today. Which parts remain durable, which depend on their historical or institutional setting, and what would need confirmation from a newer source? Following the tags and the Science & Engineering collection can reveal useful comparisons. Agreement between sources can strengthen confidence, while disagreement can point to changing definitions, methods, evidence or priorities.

Finally, decide what you need from the item: background knowledge, a quotation, a worked example, a model, a visual explanation or a starting bibliography. That purpose should guide the depth of reading and the notes you keep. Doxxly helps locate and navigate the source; careful interpretation remains the reader's responsibility.

Explore more Science & Engineering resources

Frequently asked questions about On the Worst-Case Complexity of the k-Means Method

Practical answers about reading, downloading and understanding this document on Doxxly.

More in Science & Engineering