检索结果-内蒙古大学图书馆

Socially Fair Matching: Exact and approximation algorithms 1

学校读者我要写书评

暂无评论

18th International Symposium on algorithms and Data Structures, WADS 2023

作者： Bandyapadhyay, Sayan Fomin, Fedor Inamdar, Tanmay Panolan, Fahad Simonov, Kirill Portland State University Portland United States University of Bergen Bergen Norway Indian Institute of Technology Hyderabad India Hasso Plattner Institute University of Potsdam Potsdam Germany

ISBN: (数字)9783031389061

ISBN: (纸本)9783031389054

Matching problems are some of the most well-studied problems in graph theory and combinatorial optimization, with a variety of theoretical as well as practical motivations. However, in many applications of optimization problems, a "solution" corresponds to real-life decisions that have major impact on humans belonging to diverse groups defined by attributes such as gender, race, or ethnicity. Due to this motivation, the notion of algorithmic fairness has recently emerged to prominence. Depending on specific application, researchers have introduced several notions of fairness. In this paper, we study a problem called Socially Fair Matching, which combines the traditional Minimum Weight Perfect Matching problem with the notion of social fairness that has been studied in clustering literature [Abbasi et al., and Ghadiri et al., FAccT, 2021]. In our problem, the input is an edge-weighted complete bipartite graph, where the bipartition represent two groups of entities. The goal is to find a perfect matching as well as an assignment that assigns the cost of each matched edge to one of its endpoints, such that the maximum of the total cost assigned to either of the two groups is minimized. Unlike Minimum Weight Perfect Matching, we show that Socially Fair Matching is weakly NP-hard. On the positive side, we design a deterministic PTAS for the problem when the edge weights are arbitrary. Furthermore, if the weights are integers and polynomial in the number of vertices, then we give a randomized polynomial-time algorithm that solves the problem exactly. Next, we show that this algorithm can be used to obtain a randomized FPTAS when the weights are arbitrary. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

关键词： approximation algorithms

Additive approximation algorithms for Sliding Puzzle 1

学校读者我要写书评

暂无评论

17th International Joint Conference on Theoretical Computer Science - Frontier of Algorithmic Wisdom, IJTCS-FAW 2023

作者： Zhong, Zhixian Beijing China

ISBN: (数字)9783031393440

ISBN: (纸本)9783031393433

With the development of sport sliding puzzle, it is of great significance to study better algorithms to solve sliding puzzles. Since solving the puzzle optimally is hard, we hope to find an additive approximation algorithm, that is, the length of solution output by this algorithm is at most a low-order term more than optimal solution. n× 2 rectangular puzzle, as a variation of (n2- 1 ) -puzzle, can be solved by an algorithm in divide-and-conquer scheme. We proved that it’s an additive approximation algorithm within O(nlog n) additive constant. For (n2- 1 ) -puzzle, finding a good approximation algorithm is more difficult. We designed a new poly-time algorithm to solve (n2- 1 ) -puzzle, which consists of several phases: First build the board into a "clear state", then transport the tiles in this clear state, after arranging some tiles the puzzle is divided into smaller parts, finally solve each of parts. And we proved that it is an additive approximation algorithm within O(n2.75) additive constant. Also, using these approximation algorithms, we analyzed the optimal solution length asymptotically in the average case and the worst case (God’s number). For n× 2 rectangular puzzle, the average optimal solution length is n2+ O(nlog n) and the God’s number is 2 n2+ O(nlog n). For (n2- 1 ) -puzzle, the average optimal solution length is 23n3+O(n2.75) and the God’s number is n3+ O(n2.75). © 2023, Springer Nature Switzerland AG.

关键词： approximation algorithms

approximation algorithms for k-submodular maximization subject to a knapsack constraint

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Xiao, Hao Liu, Qian Zhou, Yang Li, Min School of Mathematics and Statistics Shandong Normal University China

In this paper, we study the problem of maximizing k-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a (Equation) greedy approximation algorithm. For the non-monotone case, we are the first to consider the knapsack problem and provide a greedy-type combinatorial algorithm with approximation ratio (Equation). Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

How to Make Your approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable approximation algorithms of Functions with Low Sensitivity 26

学校读者我要写书评

暂无评论

How to Make Your Approximation Algorithm Private: A Black-Bo...

26th International Conference on approximation algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

作者： Blocki, Jeremiah Grigorescu, Elena Mukherjee, Tamalika Zhou, Samson Purdue University West LafayetteIN United States University of California BerkeleyCA United States Rice University HoustonTX United States

ISBN: (纸本)9783959772969

We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on algorithms A that output an approximation to a function f of the form (1 − α)f(x) − κ ≤ A(x) ≤ (1 + α)f(x) + κ, where κ ∈ R≥0 denotes additive error and α ∈ [0, 1) denotes multiplicative error can be"tuned" to small-enough values while incurring only a polynomial blowup in the running time/space. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function f has small "global sensitivity". We achieve these results by applying the "smooth sensitivity" framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007). Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into Ε-differentially private approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) Ε-edge differentially-private sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph whose accuracy holds with high probability. In the area of streaming algorithms, our results include Ε-DP algorithms for estimating Lp-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating Lp-norms, distinct elements, and the length of the longest increasing subsequence. © 2023 Schloss Dagstuhl- Leibniz-

关键词： approximation algorithms

approximation algorithms to Enhance Social Sharing of Fresh Point-of-Interest Information

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Li, Songhua Duan, Lingjie Singapore University of Technology and Design Singapore Singapore

In location-based social networks (LBSNs), such as Gowalla and Waze, users sense urban point-of-interest (PoI) information (e.g., restaurants' queue length and real-time traffic conditions) in the vicinity and share such information with friends in online social networks. Given each user's social connections and the severe lags in disseminating fresh PoI to all users, major LBSNs aim to enhance users' social PoI sharing by selecting k out of m users as hotspots and broadcasting their PoI information to the entire user community. This motivates us to study a new combinatorial optimization problem by integrating two urban sensing and online social networks. We prove that this problem is NP-hard and also renders existing approximation solutions not viable. Through analyzing the interplay effects between the sensing and social networks, we successfully transform the involved PoI-sharing process across two networks to matrix computations for deriving a closed-form objective, which we find holds desirable properties (e.g., submodularity and monotonicity). This finding enables us to develop a polynomial-time algorithm that guarantees a (1 - m-2 m ( k-1 k )k) approximation of the optimum. Furthermore, we allow each selected user to move around and sense more PoI information to share. To this end, we propose an augmentation-adaptive algorithm, which benefits from a resourceaugmented technique and achieves bounded approximation, ranging from 1 k (1 - 1 e ) to 1- 1 e > 0.632 by adjusting our augmentation factors. Finally, our theoretical results are corroborated by our simulation findings using both synthetic and real-world datasets across different network topologies. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for Facility Location Problem with Service Installation Costs

学校读者我要写书评

暂无评论

SSRN

SSRN 2023年

作者： Zhu, Lihao Zeng, Yiling Zhang, Li Li, Qiaoliang School of Mathematics and Statistics Hunan Normal University Changsha410081 China

We investigate two extensions of the classic facility location problem (FLP): the uncapacitated FLP with service installation costs (UFLPSC) and the soft-capacitated FLP with service installation costs (SFLPSC). Assuming that service installation costs are only related to service types, we propose a 6-approximation algorithm based on LP rounding to solve UFLPSC, and improve the approximation ratio to 5.034 through random parameter selection. For SFLPSC, under the same assumption, we first propose a 10.473-approximation algorithm, and then improve its approximation ratio to 8.091 through random parameter selection. Towards the end of the paper, a more general situation of SFLPSC is considered, where the service installation cost is related not only to service type but also to the facilities which it is installed. To solve this, an 11-approximation algorithm based on the primal-dual technique is proposed. © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for Graph Cluster Editing Problems with Cluster Size at Most 3 and 4 22nd

学校读者我要写书评

暂无评论

Approximation Algorithms for Graph Cluster Editing Problems...

22nd International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2023

作者： Il’ev, Victor Il’eva, Svetlana Dostoevsky Omsk State University Omsk Russia Sobolev Institute of Mathematics SB RAS Omsk Russia

ISBN: (纸本)9783031432569

In clustering problems, one has to partition a given set of objects into pairwise disjoint subsets (clusters) taking into account only similarity of objects. In the graph cluster editing problem similarity relation on the set of objects is given by an undirected graph whose vertices are in one-to-one correspondence with objects and edges correspond to pairs of similar objects. The goal is to find a nearest to a given graph G= (V, E) cluster graph, i.e., a graph on the vertex set V each connected component of which is a complete graph. The distance between graphs is understood as the Hamming distance between their incidence vectors. We consider a variant of the cluster editing problem in which the size of each cluster is bounded from above by a positive integer s. In 2011, Il’ev and Navrotskaya proved that this problem is NP-hard for any fixed s⩾ 3. In 2015, Puleo and Milenkovic proposed a 6-approximation algorithm for this problem. In 2016, Il’ev, Il’eva and Navrotskaya presented an approximation algorithm that is 3-approximation in case of s= 3 and 5-approximation in case of s= 4. Now we propose simple greedy-type 2-approximation algorithms for these cases with tight performance guarantees. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： approximation algorithms

approximation algorithms for Fair Range Clustering

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Hotegni, Sèdjro S. Mahabadi, Sepideh Vakilian, Ali African Institute for Mathematical Sciences-Rwanda Rwanda Microsoft Research-Redmond United States United States

This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick k centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of n points in a metric space (P, d) where each point belongs to one of the different demographics (i.e., (Equation presented)) and a set of intervals [α1, β1], · · ·, [α, β] on desired number of centers from each group, the goal is to pick a set of k centers C with minimum p-clustering cost (i.e., (Equation presented)) such that for each group i ∈ , |C ∩ Pi| ∈ [αi, βi]. In particular, the fair range p-clustering captures fair range k-center, k-median and k-means as its special cases. In this work, we provide efficient constant factor approximation algorithms for fair range p-clustering for all values of p ∈ [1, ∞). Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for Directed Weighted Spanners

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Grigorescu, Elena Kumar, Nithish Lin, Young-San Purdue University United States Melbourne Business School Australia

In the pairwise weighted spanner problem, the input consists of a weighted directed graph on n vertices, where each edge is assigned both a cost and a length. Furthermore, we are given k terminal vertex pairs and a distance constraint for each pair. The goal is to find a minimum-cost subgraph in which the distance constraints are satisfied. A more restricted variant of this problem was shown to be O(2log1−Ε n)-hard to approximate under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). This general formulation captures many well-studied network connectivity problems, including spanners, distance preservers, and Steiner forests. We study the weighted spanner problem, in which the edges have positive integral lengths of magnitudes that are polynomial in n, while the costs are arbitrary non-negative rational numbers. Our results include the following in the classical offline setting: • An Õ(n4/5+Ε)-approximation algorithm for the pairwise weighted spanner problem. When the edges have unit costs and lengths, the best previous algorithm gives an Õ(n3/5+Ε)-approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on algorithms, 2020). • An Õ(n1/2+Ε)-approximation algorithm for the weighted spanner problem when the terminal pairs consist of all vertex pairs and the distances must be preserved exactly. When the edges have unit costs and arbitrary positive lengths, the best previous algorithm gives an Õ(n1/2)-approximation for the all-pair spanner problem, due to Berman, Bhattacharyya, Makarychev, Raskhodnikova, and Yaroslavtsev (Information and Computation, 2013). We also prove the first results for the weighted spanners in the online setting. In the online setting, the terminal vertex pairs arrive one at a time, in an online fashion, and edges are required to be added irrevocably to the solution in order to satisfy the distance constraints, while approximately minimizing the cost. Our results include the followin

关键词： approximation algorithms