Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.

Fair k-Center Problem with Outliers on Massive Data

The clustering problem of big data in the era of artificial intelligence has been widely studied.Because of the huge amount of data,distributed algorithms are often used to deal with big data problems.The distributed computing model has an attractive feature:it can handle massive datasets that cannot be put into the main memory.On the other hand,since many decisions are made automatically by machines in today’s society,algorithm fairness is also an important research area of machine learning.In this paper,we study two fair clustering problems:the centralized fair k-center problem with outliers and the distributed fair k-center problem with outliers.For these two problems,we have designed corresponding constant approximation ratio algorithms.The theoretical proof and analysis of the approximation ratio,and the running space of the algorithm are given.

Approximation Algorithm for the Balanced 2-Correlation Clustering Problem

The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of data.It has significant applications in different fields,such as machine learning,biology,and data mining,and many different problems in other areas.In this paper,the Balanced 2-CorCP(B2-CorCP) is introduced and examined,and a new interesting variant of the CorCP is described.The goal of this clustering problem is to partition the vertex set into two clusters with equal size,such that the number of disagreements is minimized.We first present a polynomial time algorithm for the B2-CorCP on M-positive edge dominant graphs(M≥ 3).Then,we provide a series of numerical experiments,and the results show the effectiveness of our algorithm.

A Hashing Power Allocation Game with and without Risk-free Asset

Miners in various blockchain-backed cryptocurrency networks compete to maintain the validity of the underlying distributed ledgers to earn the bootstrapped cryptocurrencies.With limited hashing power,each miner needs to decide how to allocate their resource to different cryptocurrencies so as to achieve the best overall payoff.Together all the miners form a hashing power allocation game.We consider two settings of the game,depending on whether each miner can allocate their fund to a risk-free asset or not.We show that this game admits unique pure Nash equilibrium in closed-form for both settings.

Blockchain Technology:Theory and Applications Special Issue

Blockchain technology originated from virtual currency, which, since 2009, has sprung up all over the world and has gradually entered people’s sight. Blockchain is a new integrated application model of distributed data storage, point-to-point transmission, consensus mechanism, cryptographic algorithm and other computer technologies. In a broad sense, blockchain technology is a new distributed infrastructure and computing method by using blockchain data structure to verify and store data, distributed node consensus algorithm to generate and update data, cryptography to ensure the security of data transmission and access, and intelligent contract composed of automatic script code to program and operate data.