Optimization problems involving the minimization of a finite sum of smooth, possibly non-convex functions arise in numerous applications. To achieve a consensus solution over a network, distributed optimization algori...
详细信息
We adapt the theory of normal and special polynomials from symbolic integration to the summation setting, and then built up a general framework embracing both the usual shift case and the q-shift case. In the context ...
详细信息
We study efficient algorithms for the Euclidean k-Center problem, focusing on the regime of large k. We take the approach of data reduction by considering α-coreset, which is a small subset S of the dataset P such th...
详细信息
An extension to triangular domains of the univariate q-Bernstein basis functions is introduced and analyzed. Some recurrence relations and properties such as partition of unity and degree elevation are proved for them...
详细信息
In the 3-Hitting Set problem, the input is a hypergraph G such that the size of every hyperedge of G is at most 3, and an integers k, and the goal is to decide whether there is a set S of at most k vertices such that ...
详细信息
In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page faults in expectation. While computing ...
详细信息
We consider the problem where an active Decision-Maker (DM) is tasked to identify the true hypothesis using as few as possible observations while maintaining accuracy. The DM collects observations according to its det...
详细信息
We study memory-bounded algorithms for the k-secretary problem. The algorithm of Kleinberg [Kle05] achieves an optimal competitive ratio of 1 − O(1/√k), yet a straightforward implementation requires Ω(k) memory. Our ...
详细信息
In the classical NP-hard (metric) k-median problem, we are given a set of n clients and centers with metric distances between them, along with an integer parameter k ≥ 1. The objective is to select a subset of k open...
详细信息
In the classical NP-hard (metric) k-median problem, we are given a set of n clients and centers with metric distances between them, along with an integer parameter k ≥ 1. The objective is to select a subset of k open centers that minimizes the total distance from each client to its closest open center. In their seminal work, Jain, Mahdian, Markakis, Saberi, and Vazirani presented the Greedy algorithm for facility location, which implies a 2-approximation algorithm for k-median that opens k centers in expectation. Since then, substantial research has aimed at narrowing the gap between their algorithm and the best achievable approximation by an algorithm guaranteed to open exactly k centers, as required in the k-median problem. During the last decade, all improvements have been achieved by leveraging their algorithm (or a small improvement thereof), followed by a second step called bi-point rounding, which inherently adds an additional factor to the approximation guarantee. Our main result closes this gap: for any Ε > 0, we present a (2 + Ε)-approximation algorithm for the k-median problem, improving the previous best-known approximation factor of 2.613. Our approach builds on a combination of two key algorithms. First, we present a non-trivial modification of the Greedy algorithm that operates with only O(log n/Ε2) adaptive phases. Through a novel walk-between-solutions approach, this enables us to construct a (2 + Ε)-approximation algorithm for k-median that consistently opens at most k + O(log n/Ε2) centers: via known results, this already implies a (2 + Ε)-approximation algorithm that runs in quasi-polynomial time. Second, we develop a novel (2 + Ε)-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an Ω(Ε3/ log n) fraction. Achieving this involves several ideas, including a sampling approach inspired by the k-means++ algorithm and a reduction to submodular optimization subject t
作者：
Durán, Juan ManuelDepartment of Values
Technology and Innovation Faculty of Technology Policy and Management Delft University of Technology Jaffalaan 5 Delft2628 BX Netherlands
This chapter is interested in the epistemology of algorithms. As I intend to approach the topic, this is an issue about epistemic justification. Current approaches to justification emphasize the transparency of algori...
详细信息
暂无评论