Scholarlink

This paper introduces the min-max correlation clustering problem with penalties, which is a generalization of the correlation clustering problem. In this problem, each vertex can be clustered or penalized, and the goal of the problem is to minimize the sum of the number of error edges and the penalty cost at the worst vertex. In this paper, we give an integer programming and linear programming relaxation of the problem, and provide a constant approximation algorithm of the problem based on LP-rounding technique.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximation Algorithm for Min-max Correlation Clustering Problem with Penalties

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yuebo Huang,
  • Sai Ji,
  • Xiaoyun Tian,
  • Kun Zhou

摘要

This paper introduces the min-max correlation clustering problem with penalties, which is a generalization of the correlation clustering problem. In this problem, each vertex can be clustered or penalized, and the goal of the problem is to minimize the sum of the number of error edges and the penalty cost at the worst vertex. In this paper, we give an integer programming and linear programming relaxation of the problem, and provide a constant approximation algorithm of the problem based on LP-rounding technique.