Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the have also been combined to derive many interesting results. We survey developments in area both from algorithmic hardness perspectives, emphasis on new techniques potential future research directions.

Abstract For years, nongovernmental terrorism in Latin America was considered an epiphenomenon of the Cold War. The persistence this type political violence 1990s, however, not only belied many assumptions about its causes but also led scholars to reexamine phenomenon. This article investigates validity a number hypotheses by applying pooled time-series cross-section regression analysis data from 17 American countries between 1980 and 1995. Findings indicate that terrorist acts are more...

We consider the classic Facility Location, k-Median, and k-Means problems in metric spaces of constant doubling dimension. give first nearly linear-time approximation schemes for each problem, making a significant improvement over state-of-the-art algorithms. Moreover, we show how to extend techniques used get efficient prize-collecting k-Medians k-Means, bicriteria with outliers, outliers k-Center.

This article examines contemporary uses of terrorism in Colombia. Combining an historical analysis with the most complete database available on political violence, we illustrate how Colombia constitutes a specific strategy that can be distinguished from other manifestations violence. We argue Colombia's non-state armed groups have turned into pivotal element their repertoires action. These parties not only increased reliance this and introduced more refined forms such as de-territorialized...

This article investigates the use of terror in Colombia's civil war by examining behavior Revolutionary Armed Forces Colombia (FARC) and National Liberation Army (ELN). Relying on an extensive database covering 25 years conflict, traces way which FARC ELN have employed as part their overall insurrectional strategy. I argue that, while ideology plays important role inspiring revolutionary terrorism, these groups' practices evolved over time were driven principally military strategies....

For years, nongovernmental terrorism in Latin America was considered an epiphenomenon of the Cold War. The persistence this type political violence 1990s, however, not only belied many assumptions about its causes but also led scholars to reexamine phenomenon. This article investigates validity a number hypotheses by applying pooled time-series cross-section regression analysis data from 17 American countries between 1980 and 1995. Findings indicate that terrorist acts are more likely occur...

We study the k-BALANCED PARTITIONING problem in which vertices of a graph are to be partitioned into k sets size at most ceil(n/k) while minimising cut size, is number edges connecting different sets. The well studied for general graphs, it cannot approximated within any factor polynomial time. However, little known about restricted classes. show that trees remains surprisingly hard. In particular, approximating APX-hard even if maximum degree tree constant. If instead diameter bounded by...

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected cheapest possible way an edge-weighted graph. This problem has been extensively studied from viewpoint approximation and also parametrization. In particular, on one hand is known APX-hard, W[2]-hard other, if parameterized by number non-terminals (Steiner vertices) optimum solution. contrast this we give efficient scheme (EPAS), circumvents both hardness results. Moreover, our methods imply existence...

We consider the classic Facility Location, k -Median, and -Means problems in metric spaces of doubling dimension d . give nearly linear-time approximation schemes for each problem. The complexity our algorithms is Õ(2 (1/ε) O(d2) n) , making a significant improvement over state-of-the-art that run time n (d/ε) O(d) Moreover, we show how to extend techniques used get first efficient prize-collecting -Median bicriteria with outliers, outliers -Center.

En el presente trabajo se examina fenomeno de la muerte migrantes en corredor migratorio America del Norte, particular frontera entre Mexico y Estados Unidos, desde perspectiva los derechos humanos. Nuestro principal argumento es que actual politica migratoria estadounidense busca manera explicita disuadir a cruzar al aumentar costos riesgos cruce irregular. Al desviar flujos migratorios hacia areas mas agrestes desoladas donde encierra evidentes riesgos, las autoridades estadounidenses...

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and set {D}subseteq V x of k demand pairs. aim is to compute the cheapest network N subseteq G for which there an s -> t path each (s,t)in {D}. It known that this notoriously hard no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing runtime by [Dinur & Manurangsi, ITCS 2018]. In light this, we systematically study several special cases DSN determine their parameterized...