Limits of Schema Mappings [0.03%]
模式映射的局限性
Phokion G Kolaitis,Reinhard Pichler,Emanuel Sallinger et al.
Phokion G Kolaitis et al.
Schema mappings have been extensively studied in the context of data exchange and data integration, where they have turned out to be the right level of abstraction for formalizing data inter-operability tasks. Up to now and for the most par...
Mark Kaminski,Egor V Kostylev
Mark Kaminski
SPARQL is the standard query language for RDF data. The distinctive feature of SPARQL is the OPTIONAL operator, which allows for partial answers when complete answers are not available due to lack of information. However, optional matching ...
Motivating Time-Inconsistent Agents: A Computational Approach [0.03%]
动机与计算：解决时间 inconsistent智能体问题的新方法
Susanne Albers,Dennis Kraft
Susanne Albers
We study the complexity of motivating time-inconsistent agents to complete long term projects in a graph-based planning model proposed by Kleinberg and Oren (2014). Given a task graph G with n nodes, our objective is to guide an agent towar...
Petr A Golovach,Dieter Kratsch,Daniël Paulusma et al.
Petr A Golovach et al.
A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given ...
George Christodoulou,Stefano Leonardi,Alkmini Sgouritsa
George Christodoulou
We study the design of cost-sharing protocols for two fundamental resource allocation problems, the Set Cover and the Steiner Tree Problem, under environments of incomplete information (Bayesian model). Our objective is to design protocols ...
Marek Cygan,Marcin Pilipczuk,Michał Pilipczuk et al.
Marek Cygan et al.
Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves (2011) initiated the study of the problem of appropriately vi...
Marcin Mucha
Marcin Mucha
The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with an approxima...