# approximation algorithms

Published articles for approximation algorithms.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression

DevFeed: [Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression](<https://devfeed.tech/articles/relax-and-sparsify-approximation-algorithms-for-sparse-ridge-regression-138921.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19738>)

Author: Shixuan Yi, Yongchun Li

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [regression](<https://devfeed.tech/tags/regression.md>), [sparsity](<https://devfeed.tech/tags/sparsity.md>)

### AI overview

For sparse ridge regression in low-rank, high-dimensional settings, the paper uses a relax-and-sparsify approach: solve a convex relaxation, then sparsify its solution to meet the original constraint. It establishes a tight rank-dependent sparsity bound by dividing the relaxation's support into two parts, which motivates parameter reduction and binary redistribution strategies. In experiments on synthetic and real datasets, binary redistribution outperformed the benchmarks in most instances.

### Source excerpt

arXiv:2611.19738v1 Announce Type: cross Abstract: This paper studies sparse ridge regression in the low-rank, high-dimensional setting that often arises when data collection is expensive. By exploiting the low-rank structure, we develop approximation algorithms within a relax-and-sparsify framework: solve a convex relaxation and then sparsify its solution to satisfy the original sparsity constraint. Specifically, we establish a tight rank-dependent sparsity bound for the convex relaxation by decomposing its support into two parts. This decomposition in turn motivates two approximation strategies, parameter reduction and binary redistribution, each exploiting a different part. Experiments on synthetic and real datasets show that the binary redistribution algorithms outperform the benchmarks in most instances.

## $\\gamma$-weakly $\\theta$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions

DevFeed: [$\\gamma$-weakly $\\theta$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](<https://devfeed.tech/articles/gamma-weakly-theta-up-concavity-a-unified-framework-for-non-convex-optimization-beyond-dr-submodular-and-oss-functions-131882.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.13506>)

Author: Mohammad Pedramfar, Vaneet Aggarwal

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [actions](<https://devfeed.tech/tags/actions.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [also](<https://devfeed.tech/tags/also.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [change](<https://devfeed.tech/tags/change.md>), [class](<https://devfeed.tech/tags/class.md>), [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [condition](<https://devfeed.tech/tags/condition.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dr](<https://devfeed.tech/tags/dr.md>), [framework](<https://devfeed.tech/tags/framework.md>), [functions](<https://devfeed.tech/tags/functions.md>), [gamma](<https://devfeed.tech/tags/gamma.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [oss](<https://devfeed.tech/tags/oss.md>), [up](<https://devfeed.tech/tags/up.md>)

### AI overview

The proposed γ-weak θ-up-concavity framework covers monotone DR-submodular and One-Sided Smooth (OSS) functions, plus objectives whose marginal gains can rise before falling or that vanish faster than any power of the norm near the origin. It builds a surrogate gradient from gradients along the segment between the origin and the current point, yielding an upper-linearization inequality with a point-dependent approximation coefficient. Restricting actions to the closed convex hull of coordinate-wise maximal feasible points makes that coefficient uniformly positive, according to curvature and feasible-set geometry. Reductions to linear optimization provide offline approximation algorithms and online regret guarantees. The coefficient matches the optimal DR-submodular maximization value and improves known OSS coefficients under matroid constraints when the OSS parameter is positive.

### Source excerpt

arXiv:2602.13506v3 Announce Type: replace-cross Abstract: Many objectives in machine learning and combinatorial optimization are non-concave. We introduce $\gamma$-weak $\theta$-up-concavity, a first-order condition for nonnegative monotone functions in which a scaling function $\theta$ lets the curvature change with the size of the solution. The resulting class strictly contains monotone DR-submodular functions and One-Sided Smooth (OSS) functions. It also contains functions whose marginal gains first increase and then decrease, and functions that vanish faster than any power of the norm at the origin. We construct a surrogate gradient from gradients along the segment from the origin to the current point and prove an upper-linearization inequality with a point-dependent approximation coefficient. Restricting actions to the closed convex hull of the coordinate-wise maximal feasible points makes this coefficient uniformly positive, with a value determined by the curvature parameters and the geometry of the feasible set. Standard reductions to linear optimization then give offline approximation algorithms and online algorithms with regret guarantees. The coefficient matches the optimal one for DR-submodular maximization and improves the best known coefficients for OSS maximization over matroid constraints whenever the OSS parameter is positive.

## Tokenization: Hardness and Bicriteria Approximation Algorithms

DevFeed: [Tokenization: Hardness and Bicriteria Approximation Algorithms](<https://devfeed.tech/articles/tokenization-hardness-and-bicriteria-approximation-algorithms-132091.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.15074>)

Author: Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [tokenization](<https://devfeed.tech/topics/tokenization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-cc](<https://devfeed.tech/tags/cs-cc.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [tokenization](<https://devfeed.tech/tags/tokenization.md>)

### AI overview

Binary Tokenization selects up to K substrings from a corpus of binary strings to minimize the total tokens needed to segment each document; the single symbols 0 and 1 are always available. For total corpus length n and maximum document length M, the abstract proves that no polynomial-time n^(1−ε)-approximation exists for any fixed ε in (0,1), unless P=NP. It also gives a polynomial-time bicriteria algorithm with γ=√M log n: it uses at most γK vocabulary entries and at most γ times the optimum token count under budget K. In the storage-budget variant, where selected substring lengths sum to at most B, the stated bicriteria factors are both O(log n log B) for 2≤B<n.

### Source excerpt

arXiv:2611.15074v1 Announce Type: cross Abstract: We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(\gamma,\gamma)$-bicriteria algorithm, with $\gamma = \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $\gamma K$ with number of tokens at most $\gamma {\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B

## Approximating Minimum Dominating Set with Few Awake Rounds

DevFeed: [Approximating Minimum Dominating Set with Few Awake Rounds](<https://devfeed.tech/articles/approximating-minimum-dominating-set-with-few-awake-rounds-127791.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2608.19096>)

Author: Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju

Published: 2026-11-11T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cluster](<https://devfeed.tech/tags/cluster.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computing](<https://devfeed.tech/tags/computing.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [expectation](<https://devfeed.tech/tags/expectation.md>), [messages](<https://devfeed.tech/tags/messages.md>), [model](<https://devfeed.tech/tags/model.md>), [node](<https://devfeed.tech/tags/node.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [sampling](<https://devfeed.tech/tags/sampling.md>), [scheduling](<https://devfeed.tech/tags/scheduling.md>), [set-cover](<https://devfeed.tech/tags/set-cover.md>)

### AI overview

In the sleeping CONGEST model, the paper gives an expected O(log Δ)-approximation for Minimum Dominating Set with O(log Δ) awake rounds and O(log² Δ) total rounds, improving on prior algorithms whose awake complexity was Ω(log² Δ). For any 1 < α ≤ min{Δ, log n}, it also offers a tradeoff: expected approximation Õ(α log_α Δ), Õ(log Δ - log_α Δ) rounds, and Õ(log_α Δ) awake complexity. The results extend a CONGEST Set Cover algorithm to a two-parameter version and use sampling-based estimation and virtual binary tree scheduling. These claims come from the supplied abstract.

### Source excerpt

arXiv:2608.19096v2 Announce Type: replace Abstract: We study the Minimum Dominating Set (MDS) problem in the sleeping CONGEST model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard CONGEST model, in which a node may sleep in some rounds and can only compute, send messages, or receive messages when it is awake. The awake complexity of an algorithm in this model is the worst case number (over all inputs and all nodes) of rounds a node is awake for during the execution of the algorithm. While there are several $O(\log \Delta)$-approximation algorithms (in expectation) for MDS that run in $O(\log^2 \Delta)$ rounds, all of these have $\Omega(\log^2 \Delta)$ awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first $O(\log \Delta)$-approximation algorithm for MDS with $O(\log \Delta)$ awake complexity. The approximation guarantee holds in expectation, and the algorithm runs in $O(\log^2\Delta)$ rounds. We can reduce the awake complexity further, but at the cost of approximation: we present, for any $1<\alpha\le\min\{\Delta,\log n\}$, an algorithm in the sleeping CONGEST model that computes an $\tilde{O}(\alpha\log_\alpha\Delta)$-approximate dominating set in expectation in $\tilde{O}(\log\Delta\cdot \log_{\alpha} \Delta)$ rounds with $\tilde{O}(\log_{\alpha} \Delta)$ awake complexity. Our results depend on a generalization of the CONGEST model Set Cover algorithm of Grunau, Mitrovi\'c, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an $O(p\cdot q\cdot\log_p\Delta)$-approximate dominating set in $O(\log_p\Delta\cdot\log_q\Delta)$ rounds for parameters $1

## Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover

DevFeed: [Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover](<https://devfeed.tech/articles/simpler-logarithmic-approximation-algorithms-for-the-optimal-decision-tree-and-adaptive-set-cover-94119.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2604.12036>)

Author: Micha{\\l} Szyfelbein

Published: 2026-10-21T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [set-cover](<https://devfeed.tech/tags/set-cover.md>)

### AI overview

The paper presents a greedy algorithm for the Optimal Decision Tree problem with a simplified analysis and simultaneous approximation factors below 3.65 log₂ n for worst-case cost and 7.3 log₂ n for average-case cost, where n is the number of hypotheses. It introduces Separating Subfamily, which selects a cheapest set of tests that partitions hypotheses into sufficiently small groups, and reduces that problem to Maximum Coverage. The approach uses properties of cutting a clique into small pieces, with edges representing hypothesis pairs to separate. The paper also applies ODT to Adaptive Set Cover, giving an O(log(k-n))-approximation, where k is the number of possible realizations.

### Source excerpt

arXiv:2604.12036v4 Announce Type: replace-cross Abstract: We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tree (ODT) problem has been extensively studied in the literature, and $\mathcal{O}(\log n)$-approximation guarantees are known for each criterion, including a simultaneous guarantee for both (here $n$ is the number of hypotheses) [ICML]. Although most of the existing algorithm use simple greedy strategies, their analyses rely on intricate arguments. Since ODT is a fundamental problem with wide-ranging applications, we are interested in developing algorithms that are both effective and easy to understand. We present a new greedy algorithm with a simplified analysis that simultaneously achieves approximation factors below $3.65\log_2 n$ for worst-case cost and $7.3\log_2 n$ for average-case cost. Our algorithm for the Optimal Decision Tree behaves greedily with respect to the hereby introduced Separating Subfamily problem which asks for the cheapest subfamily of tests which partitions the hypotheses into pieces of small enough size. We show that the Separating Subfamily can itself be reduced to an instance of the well-known Maximum Coverage problem. At the core of our approach lies exploiting properties of cutting a clique into small pieces, where edges represent pairs of hypotheses to be separated. In the spirit of simplicity, we also provide a new and straightforward application of ODT: an $\mathcal{O}(\log (k\cdot n))$-approximation for the Adaptive Set Cover problem, where $k$ is the number of possible realizations.

## Hashing to Estimate the Size of a Stream

DevFeed: [Hashing to Estimate the Size of a Stream](<https://devfeed.tech/articles/hashing-to-estimate-the-size-of-a-stream-40394.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2016/01/04/hashing-to-estimate-the-size-of-a-stream/>)

Published: 2016-01-04T09:00:37Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [hashing](<https://devfeed.tech/topics/hashing.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [data](<https://devfeed.tech/topics/data.md>), [Python](<https://devfeed.tech/topics/python.md>), [Parallelism](<https://devfeed.tech/topics/parallelism.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [data](<https://devfeed.tech/tags/data.md>), [hashing](<https://devfeed.tech/tags/hashing.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [sublinear-algorithms](<https://devfeed.tech/tags/sublinear-algorithms.md>)

### AI overview

This article explains how random hash functions can estimate the number of distinct items in a data stream that is too large to fit in memory. It presents a Python implementation using minimum hash values and parallel hashes to reduce variance, and states approximation guarantees for the estimate.

### Source excerpt

Problem: Estimate the number of distinct items in a data stream that is too large to fit in memory. Solution: (in python) import random def randomHash(modulus): a, b = random.randint(0,modulus-1), random.randint(0,modulus-1) def f(x): return (a*x + b) % modulus return f def average(L): return sum(L) / len(L) def numDistinctElements(stream, numParallelHashes=10): modulus = 2**20 hashes = [randomHash(modulus) for _ in range(numParallelHashes)] minima = [modulus] * numParallelHashes currentEstimate = 0 for i in stream: hashValues = [h(i) for h in hashes] for i, newValue in enumerate(hashValues): if newValue < minima[i]: minima[i] = newValue currentEstimate = modulus / average(minima) yield currentEstimate Discussion: The technique used here is to use random hash functions.

## The Many Faces of Set Cover

DevFeed: [The Many Faces of Set Cover](<https://devfeed.tech/articles/the-many-faces-of-set-cover-40382.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/05/04/the-many-faces-of-set-cover/>)

Published: 2015-05-04T09:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Regular expression](<https://devfeed.tech/topics/regular-expression.md>), [Database](<https://devfeed.tech/topics/database.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [expression](<https://devfeed.tech/tags/expression.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [np](<https://devfeed.tech/tags/np.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [programming](<https://devfeed.tech/tags/programming.md>), [regex](<https://devfeed.tech/tags/regex.md>), [regex-golf](<https://devfeed.tech/tags/regex-golf.md>), [regular-expressions](<https://devfeed.tech/tags/regular-expressions.md>), [set-cover](<https://devfeed.tech/tags/set-cover.md>)

### AI overview

This tutorial explains the set cover problem and connects it to regex golf. It shows how selected regular expressions can be combined to cover desired strings while avoiding unwanted matches, and notes that set cover is NP-hard, motivating approximation algorithms.

### Source excerpt

A while back Peter Norvig posted a wonderful pair of articles about regex golf. The idea behind regex golf is to come up with the shortest possible regular expression that matches one given list of strings, but not the other. "Regex Golf," by Randall Munroe. In the first article, Norvig runs a basic algorithm to recreate and improve the results from the comic, and in the second he beefs it up with some improved search heuristics.

## When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation

DevFeed: [When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation](<https://devfeed.tech/articles/when-greedy-algorithms-are-good-enough-submodularity-and-the-1-1-e-approximation-40361.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/07/07/when-greedy-algorithms-are-good-enough-submodularity-and-the-1-1e-approximation/>)

Published: 2014-07-07T10:00:01Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [coverage](<https://devfeed.tech/tags/coverage.md>), [greedy](<https://devfeed.tech/tags/greedy.md>), [greedy-algorithm](<https://devfeed.tech/tags/greedy-algorithm.md>), [matroids](<https://devfeed.tech/tags/matroids.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [submodularity](<https://devfeed.tech/tags/submodularity.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

This article explains when greedy algorithms can produce optimal or near-optimal solutions. It introduces submodularity as a diminishing-returns property and discusses how it can provide a reasonably good approximation to the optimal solution.

### Source excerpt

Greedy algorithms are among the simplest and most intuitive algorithms known to humans. Their name essentially gives their description: do the thing that looks best right now, and repeat until nothing looks good anymore or you're forced to stop. Some of the best situations in computer science are also when greedy algorithms are optimal or near-optimal. There is a beautiful theory of this situation, known as the theory of matroids. We haven't covered matroids on this blog (edit: we did), but in this post we will focus on the next best thing: when the greedy algorithm guarantees a reasonably good approximation to the optimal solution.

## Community Detection in Graphs -- a Casual Tour

DevFeed: [Community Detection in Graphs -- a Casual Tour](<https://devfeed.tech/articles/community-detection-in-graphs-a-casual-tour-40357.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/05/19/community-detection-in-graphs-a-casual-tour/>)

Published: 2014-05-19T10:00:32Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cliques](<https://devfeed.tech/tags/cliques.md>), [clustering](<https://devfeed.tech/tags/clustering.md>), [community-detection](<https://devfeed.tech/tags/community-detection.md>), [erdos-renyi](<https://devfeed.tech/tags/erdos-renyi.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [modularity](<https://devfeed.tech/tags/modularity.md>), [network](<https://devfeed.tech/tags/network.md>), [newman](<https://devfeed.tech/tags/newman.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [power-law-distribution](<https://devfeed.tech/tags/power-law-distribution.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [randomized-algorithm](<https://devfeed.tech/tags/randomized-algorithm.md>), [technical](<https://devfeed.tech/tags/technical.md>), [walktrap](<https://devfeed.tech/tags/walktrap.md>)

### AI overview

This introductory article examines community detection in graphs. It explains the informal idea of a community, why defining one precisely and usefully is difficult, and how the clique-based approach leads to computationally intractable problems, including the NP-hardness of finding the largest clique.

### Source excerpt

Graphs are among the most interesting and useful objects in mathematics. Any situation or idea that can be described by objects with connections is a graph, and one of the most prominent examples of a real-world graph that one can come up with is a social network. Recall, if you aren't already familiar with this blog's gentle introduction to graphs, that a graph $ G$ is defined by a set of vertices $ V$, and a set of edges $ E$, each of which connects two vertices.

## On Coloring Resilient Graphs

DevFeed: [On Coloring Resilient Graphs](<https://devfeed.tech/articles/on-coloring-resilient-graphs-40346.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/02/21/on-coloring-resilient-graphs/>)

Published: 2014-02-21T08:45:39Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [greedy-algorithm](<https://devfeed.tech/tags/greedy-algorithm.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [research](<https://devfeed.tech/tags/research.md>), [resilience](<https://devfeed.tech/tags/resilience.md>)

### AI overview

An informal explanation of graph coloring, including why deciding 3-colorability is considered NP-hard and several graph properties that can make coloring problems easier. The article also announces the author's paper on resilient graphs.

### Source excerpt

I'm pleased to announce that another paper of mine is finished. This one just got accepted to MFCS 2014, which is being held in Budapest this year (this whole research thing is exciting!). This is joint work with my advisor, Lev Reyzin. As with my first paper, I'd like to explain things here on my blog a bit more informally than a scholarly article allows. A Recent History of Graph Coloring One of the first important things you learn when you study graphs is that coloring graphs is hard.