Analyzing clickthrough log data is important for improving search performance as well as understanding user behaviors. In this paper, we propose a novel collaborative ranking model to tackle two difficulties in analyzing clickthrough log. First, previous studies have shown that users tend to click top-ranked results even they are less relevant. Therefore, we use pairwise ranking relation to avoid the position bias in clicks. Second, since click data are extremely sparse with respect to each query or user, we construct a collaboration model to eliminate the sparseness problem. We also find that the proposed model and previous popular used click-based models address different aspects of clickthrough log data. We further propose a hybrid model that can achieve significant improvement compared to the baselines on a large-scale real world dataset.

PCS is a CSP solver that can produce a machine-checkable deductive proof in case it decides that the input problem is unsatisfiable. The roots of the proof may be nonclausal constraints, whereas the rest of the proof is based on resolution of signed clauses, ending with the empty clause. PCS uses parameterized, constraint-specific inference rules in order to bridge between the nonclausal and the clausal parts of the proof. The consequent of each such rule is a signed clause that is 1) logically implied by the nonclausal premise, and 2) strong enough to be the premise of the consecutive proof steps. The resolution process itself is integrated in the learning mechanism, and can be seen as a generalization to CSP of a similar solution that is adopted by competitive SAT solvers.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w*+1), 2k/n) of the optimal CS, where w* is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.

We present an algorithm that exploits the complimentary benefits of best-first search (BFS) and depth-first search (DFS) by performing limited DFS lookaheads from the frontier of BFS. We show that this continuum requires significantly less memory than BFS. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. We demonstrate this idea for breadth-first search and for A*. Additionally, we show that when using inconsistent heuristics, Bidirectional Pathmax (BPMX), can be implemented very easily on top of the lookahead phase. Experimental results on several domains demonstrate the benefits of all our ideas.

However, there are many domains, work that is perhaps closest to ours is the "dead-end heuristic" such as map-based searches (common in GPS navigation, introduced by Björnsson and Halldórsson (2006). They computer games, and robotics) where the entire use a preprocessing phase to identify areas that are deadends, state-space is given explicitly. Optimal paths for such domains and create an abstract graph whose nodes are these can be found relatively quickly with simple heuristics, areas. Initially, the search is performed on the abstracted especially when compared to the time it takes to explore graph. The areas that were not visited during the search exponentially large combinatorial problems. Relative on the abstracted graph are then ignored when the search is quickness, however, might still not be fast enough in certain performed in the original search space. In addition to identifying real-time applications, where further improvement towards dead-ends, our approach also identifies (and prunes, high-speed performance is especially valued.

State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) frequently use an upper bound based on a partition P of a graph into independent sets for a maximum clique of the graph, which cannot be very tight for imperfect graphs. In this paper we propose a new encoding from Maxclique into MaxSAT and use MaxSAT technology to improve the upper bound based on the partition P. In this way, the strength of specific algorithms for Maxclique in partitioning a graph and the strength of MaxSAT technology in propositional reasoning are naturally combined to solve Maxclique. Experimental results show that the approach is very effective on hard random graphs and on DIMACS Maxclique benchmarks, and allows to close an open DIMACS problem.

Weighted Constraint Satisfaction is made practical by powerful consistency techniques, such as AC*, FDAC* and EDAC*, which reduce search space effectively and efficiently during search, but they are designed for only binary and ternary constraints. To allow soft global constraints, usually of high arity, to enjoy the same benefits, Lee and Leung give polynomial time algorithms to enforce generalized AC* (GAC*) and FDAC* (FDGAC*) for projection-safe soft non-binary constraints. Generalizing the stronger EDAC* is less straightforward. In this paper, we first reveal the oscillation problem when enforcing EDAC* on constraints sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary constraints. Weak EDGAC* is stronger than FDGAC* and GAC*, but weaker than VAC and soft k -consistency for k > 2. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal.

Depth-first proof-number search (df-pn) is powerful AND/OR tree search to solve positions in games. However, df-pn has a notorious problem of infinite loops when applied to domains with repetitions. Df-pn(r) cures it by ignoring proof and disproof numbers that may lead to infinite loops. This paper points out that df-pn(r) has a serious issue of underestimating proof and disproof numbers, while it also suffers from the overestimation problem occurring in directed acyclic graph. It then presents two practical solutions to these problems. While bypassing infinite loops, the threshold controlling algorithm (TCA) solves the underestimation problem by increasing the thresholds of df-pn. The source node detection algorithm (SNDA) detects the cause of overestimation and modifies the computation of proof and disproof numbers. Both TCA and SNDA are implemented on top of df-pn to solve tsume-shogi (checkmating problem in Japanese chess). Results show that df-pn with TCA and SNDA is far superior to df-pn(r). Our tsume-shogi solver is able to solve several difficult positions previously unsolved by any other solvers.

The depth first proof number search (df-pn) is an effective and popular algorithm for solving and-or tree problems by using proof and disproof numbers. This paper presents a simple but effective parallelization of the df-pn search algorithm for a shared-memory system. In this parallelization, multiple agents autonomously conduct the df-pn with a shared transposition table. For effective cooperation of agents, virtual proof and disproof numbers are introduced for each node, which is an estimation of future proof and disproof numbers by using the number of agents working on the node's descendants as a possible increase. Experimental results on large checkmate problems in shogi, which is a popular chess variant in Japan, show that reasonable increases in speed were achieved with small overheads in memory.

We present a fast local search algorithm that finds an improved solution (if there is any) in the k-exchange neighborhood of the given solutionto an instance of Weighted Feedback Arc Set in Tournaments. More precisely,given an arc weighted tournament T on n vertices and a feedback arc set F (a set of arcs whose deletion from T turns it into a directed acyclic graph), our algorithm decides in time O(2 o ( k ) n log n) if there is a feedback arc set of smaller weight and that differs from F in at most k arcs. To our knowledge this is the first algorithm searching the k -exchange neighborhood of an NP-complete problem that runs in (parameterized) subexponential time. Using this local search algorithm for Weighted Feedback Arc Set in Tournaments, we obtain subexponential time algorithms for a local search variant of Kemeny Ranking — a problem in social choice theory and of One-Sided Cross Minimization — a problem in graph drawing.