惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园_首页
Microsoft Azure Blog
Microsoft Azure Blog
aimingoo的专栏
aimingoo的专栏
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
阮一峰的网络日志
阮一峰的网络日志
Martin Fowler
Martin Fowler
B
Blog
The GitHub Blog
The GitHub Blog
T
Tailwind CSS Blog
Stack Overflow Blog
Stack Overflow Blog
L
LangChain Blog
H
Hackread – Cybersecurity News, Data Breaches, AI and More
D
DataBreaches.Net
月光博客
月光博客
人人都是产品经理
人人都是产品经理
IT之家
IT之家
GbyAI
GbyAI
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
WordPress大学
WordPress大学
博客园 - Franky
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
The Cloudflare Blog
C
Check Point Blog
罗磊的独立博客

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Improved Approximation for Maximum Edge Colouring Problem
L Sunil Chandran, Abhiruk Lahiri, Nitin Singh · 2019-10-25 · via cs.DS updates on arXiv.org

The anti-Ramsey number, $ar(G, H)$ is the minimum integer $k$ such that in any edge colouring of $G$ with $k$ colours there is a rainbow subgraph isomorphic to $H$, i.e., a copy of $H$ with each of its edges assigned a different colour. The notion was introduced by Erd{ö}s and Simonovits in 1973. Since then the parameter has been studied extensively in combinatorics, also the particular case when $H$ is a star graph. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge $q$-colouring problem. In this paper, we study the maximum edge $2$-colouring problem from the approximation algorithm point of view. The case $q=2$ is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for $q\ge 2$. For the case of $q=2$, it is also known that no polynomial-time algorithm can approximate to a factor less than $3/2$ assuming the unique games conjecture. Feng et al. showed a $2$-approximation algorithm for this problem. Later Adamaszek and Popa presented a $5/3$-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say $M$) and different colours to the connected components of $G \setminus M$. In this article, we give a new analysis of the aforementioned algorithm leading to an improved approximation bound for triangle-free graphs with perfect matching. We also show a new lower bound when the input graph is triangle-free. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above.