[Jairsubscribers] 5 new articles published by JAIR

jair-ed@isi.edu jair-ed at isi.edu
Wed Mar 1 20:52:20 PST 2017

Dear JAIR subscriber:

This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.)

If you are receiving this email in a digest format of multiple messages, you may wish to turn off the digest option to get shorter emails every month by visiting <http://mailman.isi.edu/mailman/listinfo/jairsubscribers> and setting the digest to option to "Off".

I. New JAIR Articles

Yiyuan  Wang, Shaowei  Cai and Minghao  Yin (2017)
  "Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function",
   Volume 58, pages 267-295

   For quick access go to <http://www.jair.org/papers/paper5205.html>

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.

G&#225;bor  Erd&#233;lyi, Martin  Lackner and Andreas  Pfandler (2017)
  "Computational Aspects of Nearly Single-Peaked Electorates",
   Volume 58, pages 297-337

   For quick access go to <http://www.jair.org/papers/paper5210.html>

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.

In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we  explore the relations between the new notions introduced in this paper and existing notions from the literature.

Manuel  Bodirsky and Peter  Jonsson (2017)
  "A Model-Theoretic View on Qualitative Constraint Reasoning",
   Volume 58, pages 339-385

   For quick access go to <http://www.jair.org/papers/paper5260.html>

Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.

Supriyo  Ghosh, Pradeep  Varakantham, Yossiri  Adulyasak and Patrick  Jaillet (2017)
  "Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems",
   Volume 58, pages 387-430

   For quick access go to <http://www.jair.org/papers/paper5308.html>

Bike Sharing Systems (BSSs) are widely adopted in major cities of the world due to concerns associated with extensive private vehicle usage, namely, increased carbon emissions, traffic congestion and usage of nonrenewable resources. In a BSS, base stations are strategically placed throughout a city and each station is stocked with a pre-determined number of bikes at the beginning of the day. Customers hire the bikes from one station and return them at another station. Due to unpredictable movements of customers hiring bikes, there is either congestion (more than required) or starvation (fewer than required) of bikes at base stations. Existing data has shown that congestion/starvation is a common phenomenon that leads to a large number of unsatisfied customers resulting in a significant loss in customer demand. In order to tackle this problem, we propose an optimisation formulation to reposition bikes using vehicles while also considering the routes for vehicles and future expected demand. Furthermore, we contribute two approaches that rely on decomposability in the problem (bike repositioning and vehicle routing) and aggregation of base stations to reduce the computation time significantly. Finally, we demonstrate the utility of our approach by comparing against two benchmark approaches on two real-world data sets of bike sharing systems. These approaches are evaluated using a simulation where the movements of customers are generated from real-world data sets.

Gadi  Aleksandrowicz, Hana  Chockler, Joseph  Y. Halpern and Alexander  Ivrii (2017)
  "The Computational Complexity of Structure-Based Causality",
   Volume 58, pages 431-451

   For quick access go to <http://www.jair.org/papers/paper5229.html>

Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X = x is a cause of Y = y is NP-complete in binary models (where all variables can take on only two values) and &#931;^P_2 -complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed out by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing whether {X} = {x} is a cause of Y = y. To characterize the complexity, a new family D_k^P , k = 1, 2, 3, . . ., of complexity classes is introduced, which generalises the class DP introduced by Papadimitriou and Yannakakis (DP is just D_1^P). We show that the complexity of computing causality under the updated definition is D_2^P -complete.

Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame, and characterized the complexity of determining the degree of responsibility and blame using the original definition of causality. Here, we completely characterize the complexity using the updated definition of causality. In contrast to the results on causality, we show that moving to the updated definition does not result in a difference in the complexity of computing responsibility and blame.

II. Unsubscribing from our Mailing List

To remove yourself from the JAIR subscribers mailing list, visit our
Web site (http://www.jair.org/), follow the link "notify me of new
articles", enter your email address in the form at the bottom of the
page, and follow the directions.  In the event that you've already
deleted yourself from the list and we keep sending you messages like
this one, send mail to jair-ed at isi.edu.


More information about the Jairsubscribers mailing list