Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
48
0
0.0
(
0
)
Added by
Yuhao Yao
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agents cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. We design a deterministic strategyproof mechanism for the problem with approximation ratio of 2.75, improving upon the earlier best ratio of n/2+1.
rate research
Read More
We study the multistage $K$-facility reallocation problem on the real line, where we maintain $K$ facility locations over $T$ stages, based on the stage-dependent locations of $n$ agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. $K$-facility reallocation was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online $K$-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical $K$-server problem, we present a constant-competitive algorithm for $K = 2$ facilities.
In this paper, we consider the colorful $k$-center problem, which is a generalization of the well-known $k$-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius $rho$, such that with $k$ balls of radius $rho$, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a pseudo-approximation algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.
We study dynamic matching in an infinite-horizon stochastic market. While all agents are potentially compatible with each other, some are hard-to-match and others are easy-to-match. Agents prefer to be matched as soon as possible and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that the market composition is a key factor in the desired matching technology and prioritization level. When hard-to-match agents arrive less frequently than easy-to-match ones (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching and prioritization has no impact. We further conduct comparative statics on arrival rates. Somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing arrival rate has a non-monotone effect on waiting times, due to the fact that, under some market compositions, there is an adverse effect of competition. Our comparative statics shed light on the impact of merging markets and attracting altruistic agents (that initiate chains) or easy-to-match agents. This work uncovers fundamental differences between heterogeneous and homogeneous dynamic markets, and potentially helps policy makers to generate insights on the operations of matching markets such as kidney exchange programs.
We give two fully dynamic algorithms that maintain a $(1+varepsilon)$-approximation of the weight $M$ of the minimum spanning forest of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 log W}/{varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes $Omega(log n)$ time per operation to maintain the exact weight of the MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+varepsilon)$-approximate weight of the MSF requires super constant time per operation, if $Wgeq (log n)^{omega_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(frac{1}{varepsilon^4}log^3(frac{1}{varepsilon}))$ update time if $W$ is not too large, more specifically, if $W= O({(m^*)^{1/6}}/{log n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement this result by showing that for any constant $varepsilon,alpha>0$ and $W=n^{alpha}$, any (randomized) data structure that dynamically maintains the weight of the MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Omega(varepsilon m^*)$ within a multiplicative factor of $(1+varepsilon)$ takes $Omega(log n)$ time per operation.
MAX CLIQUE problem (MCP) is an NPO problem, which asks to find the largest complete sub-graph in a graph $G, G = (V, E)$ (directed or undirected). MCP is well known to be $NP-Hard$ to approximate in polynomial time with an approximation ratio of $1 + epsilon$, for every $epsilon > 0$ [9] (and even a polynomial time approximation algorithm with a ratio $n^{1 - epsilon}$ has been conjectured to be non-existent [2] for MCP). Up to this date, the best known approximation ratio for MCP of a polynomial time algorithm is $O(n(log_2(log_2(n)))^2 / (log_2(n))^3)$ given by Feige [1]. In this paper, we show that MCP can be approximated with a constant factor in polynomial time through approximation ratio preserving reductions from MCP to MAX DNF and from MAX DNF to MIN SAT. A 2-approximation algorithm for MIN SAT was presented in [6]. An approximation ratio preserving reduction from MIN SAT to min vertex cover improves the approximation ratio to $2 - Theta(1/ sqrt{n})$ [10]. Hence we prove false the infamous conjecture, which argues that there cannot be a polynomial time algorithm for MCP with an approximation ratio of any constant factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
