Linear Sum Assignment Problem (LSAP) consists in mapping two sets of points of equal sizes according to a matrix encoding the cost of mapping each pair of points. The Linear Sum Assignment Problem with Edition (LSAPE)...
详细信息
ISBN:
(数字)9781665490627
ISBN:
(纸本)9781665490627
Linear Sum Assignment Problem (LSAP) consists in mapping two sets of points of equal sizes according to a matrix encoding the cost of mapping each pair of points. The Linear Sum Assignment Problem with Edition (LSAPE) extends this problem by allowing the mapping of sets of different sizes and adding the possibility to reject some matchings. This problem is set up by a rectangular cost matrix whose last column and last line encode the costs of rejecting the match of an element of respectively the first and the second sets. LSAPE has been the workhorse of many fundamental graph problems such as graph edit distance, median graph computation or sub graph matching. LSAP may be solved using the Hungarian algorithm while an equivalent efficient discrete algorithm has been designed for LSAPE. However, while the Sinkhorn algorithm constitutes a continuous solver for LSAP, no such algorithm yet exists for LSAPE. This lack of solvers forbids the integration of LSAPE in Neural networks requiring continuous operations from the input to the final loss. This paper aims at providing such a solver, hence paving the way to an integration of LSAPE solvers in Neural Networks.
The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence....
详细信息
ISBN:
(纸本)1577358872
The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence. Its meaningfulness is due to axiomatic properties that only the Shapley value satisfies, which, however, comes at the expense of an exact computation growing exponentially with the number of agents. Accordingly, a number of works are devoted to the efficient approximation of the Shapley value, most of them revolve around the notion of an agent's marginal contribution. In this paper, we propose with SVARM and Stratified SVARM two parameter-free and domain-independent approximation algorithms based on a representation of the Shapley value detached from the notion of marginal contribution. We prove unmatched theoretical guarantees regarding their approximation quality and provide empirical results including synthetic games as well as common explainability use cases comparing ourselves with state-of-the-art methods.
We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized....
详细信息
ISBN:
(纸本)9798331516758;9798331516741
We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a log(1+o(1)) (n) approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved log(1+o(1)) (n) approximation for computing the pathwidth of a graph.
Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a ...
详细信息
ISBN:
(纸本)9783031710322;9783031710339
Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called k-times bin-packing (kBP), where the goal is to pack the items such that each item appears exactly k times, in k different bins. We generalize some existing approximation algorithms for bin-packing to solve kBP, and analyze their performance ratio. The study of kBP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k. We also show that k-times bin-packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem. Due to space constraints, several parts of the paper were moved to appendices. All appendices are available in the full version [1].
We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that r...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.372+ epsilon approximation. In developing this result we also improve the approximation guarantee of the capacitated facility location problem with uniform facility costs. Our local search algorithm is extremely simple to analyze and is a 3.732+epsilon approximation thus improving on the 4-approximation of Kao [12].
The biharmonic distance (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In s...
详细信息
ISBN:
(纸本)9798400704901
The biharmonic distance (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error epsilon in time O(1/epsilon(2)poly(log n/epsilon)). Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms.
This paper concerns bias and asymptotic statistics for stochastic approximation (SA) driven by Markovian noise. This extended abstract is organized into three parts: 1. Background, 2. Asymptotic statistics with Markov...
详细信息
ISBN:
(数字)9798350399981
ISBN:
(纸本)9798350399981
This paper concerns bias and asymptotic statistics for stochastic approximation (SA) driven by Markovian noise. This extended abstract is organized into three parts: 1. Background, 2. Asymptotic statistics with Markovian noise, 3. Quasi stochastic approximation.
Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set F subset of V is given with the restriction C subset of F, the best known hardness for these two versions are 1+1/e approximate to 1.36 and 1+2/e approximate to 1.73 respectively, using the same reduction from Maximum k-Coverage. We prove the following two results separating them. 1. We give a 1.546-parameterized approximation algorithm that runs in time f(k)n(O(1)). Since 1+ 2/e is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original k-Median from the supplier version. 2. We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new finegrained hardness of Maximum k-Coverage for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.
We study the computational problems associated with maximizing various welfare objectives-namely utilitarian welfare, egalitarian welfare, and Nash welfare-in perpetual voting, a sequential collective decision-making ...
详细信息
ISBN:
(纸本)1577358872
We study the computational problems associated with maximizing various welfare objectives-namely utilitarian welfare, egalitarian welfare, and Nash welfare-in perpetual voting, a sequential collective decision-making framework. Prior work look into notions of fairness over time and study extensions of single-round voting rules to the multi-round setting. We show that while a utilitarian-welfare maximizing outcome can be computed efficiently, an outcome that maximizes egalitarian or Nash welfare is computationally intractable, even in the case of two candidates. We complement this by showing that maximizing egalitarian welfare is fixed-parameter tractable in the number of agents, and maximizing egalitarian or Nash welfare is W[2]-hard and slicewise polynomial in the number of timesteps. We also provide an approximation algorithm for maximizing egalitarian welfare and study strategyproofness with respect to these welfare objectives. Finally, we show that a simple greedy algorithm can achieve approximate proportionality in this setting.
We present a scalable algorithm for the individually fair (p, k)-clustering problem introduced by Jung et al. (2020) and Mahabadi and Vakilian (2020). Given n points P in a metric space, let delta(x) for x is an eleme...
详细信息
We present a scalable algorithm for the individually fair (p, k)-clustering problem introduced by Jung et al. (2020) and Mahabadi and Vakilian (2020). Given n points P in a metric space, let delta(x) for x is an element of P be the radius of the smallest ball around x containing at least n=k points. A clustering is then called individually fair if it has centers within distance delta(x) of x for each x is an element of P. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in (O) over tilde (nk2) time and obtains a bicriteria (O(1);6) approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
暂无评论