803 research outputs found
Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
Full text linkWe study integer linear programs (ILP) of the form min{c^⊤ x | Ax = b,l ≤ x ≤ u,x ∈ ℤⁿ} and analyze their parameterized complexity with respect to their distance to the generalized matching problem, following the well-established approach of capturing the hardness of a problem by the distance to triviality. The generalized matching problem is an ILP where each column of the constraint matrix has 1-norm of at most 2. It captures several well-known polynomial time solvable problems such as matching and flow problems. We parameterize by the size of variable and constraint backdoors, which measure the least number of columns or rows that must be deleted to obtain a generalized matching ILP. This extends generalized matching problems by allowing a parameterized number of additional arbitrary variables or constraints, yielding a novel parameter.
We present the following results: (i) a fixed-parameter tractable (FPT) algorithm for ILPs parameterized by the size p of a minimum variable backdoor to generalized matching; (ii) a randomized slice-wise polynomial (XP) time algorithm for ILPs parameterized by the size h of a minimum constraint backdoor to generalized matching as long as c and A are encoded in unary; (iii) we complement (ii) by proving that solving an ILP is W[1]-hard when parameterized by h even when c,A,l,u have coefficients of constant size. To obtain (i), we prove a variant of lattice-convexity of the degree sequences of weighted b-matchings, which we study in the light of SBO jump M-convex functions. This allows us to model the matching part as a polyhedral constraint on the integer backdoor variables. The resulting ILP is solved in FPT time using an integer programming algorithm. For (ii), the randomized XP time algorithm is obtained by pseudo-polynomially reducing the problem to the exact matching problem. To prevent an exponential blowup in terms of the encoding length of b, we bound the Graver complexity of the constraint matrix and employ a Graver augmentation local search framework. The hardness result (iii) is obtained through a parameterized reduction from ILP with h constraints and coefficients encoded in unary
Accepting Optimally in Automated Negotiation with Incomplete Information (abstract)
No full textIntelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
Recommended from our members
Episode #2: Interview with President Koen Lenaerts
Full text linkEpisode #2 of the Borderlines CJEU Series features CJEU President Koen Lenaerts in conversation with Professor Katerina Linos (Berkeley) and Professor Mark Pollack (Temple University). President Lenaerts has been re-elected to the Court’s top office by his peers three times since 2015, having served tirelessly since his nomination to the CJEU in 2003 by home country of Belgium. His interview traces the historic path to today’s Court of Justice, and illuminates differences from other courts, including the U.S. federal judicial system.Listeners will come away with an overview of the Court’s functions and structural methodology in interpreting the EU legal order, including the role of the President, the Judge rapporteur, and the Advocate General. Presidential responsibilities include assigning cases to Judges and presiding over the Grand Chamber to deal with the most important cases. New developments in case law, evolving technological access, and finding balance between unity and diversity, privacy and security, are addressed by the head of the EU’s judicial institution.President Lenaerts in total has spent 35 years as a European Union Judge, initially serving on the Court of First Instance of the European Communities (now the General Court) when it was established in 1989. He earned his legal degrees including a doctorate in Belgium and also obtained a Masters of Laws and a Masters in Public Administration from Harvard University. President Lenaerts is Professor of European Union Law at Leuven University in Belgium and a member of many legal and academic associations including the Academia Europaea, London; the Advisory Council of the British Institute of International and Comparative Law; the Advisory Board of the Centre of Law and Governance in Europe, University College London; the Governing Board of the Foundation of the Academy of European Law (ERA), Trier; and the Board of Trustees of the Max-Planck-Institut für ausländisches öffentliches Recht und Völkerrecht, Heidelberg. He is the recipient of numerous awards and author of a vast list of publications.</p
Correction to: Decisional Balance Inventory (DBI) Adolescent Form for Smoking: Psychometric Properties of the Persian Version
No full textCorrection After publication of the article [1], it has been brought to our attention that the first and last names of the third author were transposed in the original article. The author was published as “Ponnet Koen” where in fact the correct name is “Koen Ponnet”. The original article has been revised to reflect this
Designing robot behavior to stimulate self-disclosure of introverted and extraverted children during an initial interaction
No full textThe purpose of this thesis is to design robot behavior that stimulates self-disclosure of introverted and extraverted children during an initial interaction. This was done by designing two styles of robot behavior. One behavior style that was specifically adapted to introverted children and one behavior style that was specifically adapted to extraverted children. 41 children interacted with one of the two styles of robot behavior, using a 2 x 2 between subjects design, with child extraversion (extravert vs. introvert) and robot adaptation (behavior style matched with child’s extraversion level vs. behavior style not matched with child’s extraversion level). No significant effect of child extraversion or robot adaptation were found. However, our design did enable the robot to interact autonomously with children. Our design thus can be a building block for future design iterations.Computer Science | Data Science and Technolog
Acceptance conditions in automated negotiation
No full textIn every negotiation with a deadline, one of the negotiating parties has to accept an offer to avoid a break off. A break off is usually an undesirable outcome for both parties, therefore it is important that a negotiator employs a proficient mechanism to decide under which conditions to accept. When designing such conditions one is faced with the acceptance dilemma: accepting the current offer may be suboptimal, as better offers may still be presented. On the other hand, accepting too late may prevent an agreement from being reached, resulting in a break off with no gain for either party. Motivated by the challenges of bilateral negotiations between automated agents and by the results and insights of the automated negotiating agents competition (ANAC), we classify and compare state-of-the-art generic acceptance conditions. We focus on decoupled acceptance conditions, i.e. conditions that do not depend on the bidding strategy that is used. We performed extensive experiments to compare the performance of acceptance conditions in combination with a broad range of bidding strategies and negotiation domains. Furthermore we propose new acceptance conditions and we demonstrate that they outperform the other conditions that we study. In particular, it is shown that they outperform the standard acceptance condition of comparing the current offer with the offer the agent is ready to send out. We also provide insight in to why some conditions work better than others and investigate correlations between the properties of the negotiation environment and the efficacy of acceptance conditions.MediamaticsElectrical Engineering, Mathematics and Computer Scienc
Measuring Safety Culture Using an Integrative Approach: The Development of a Comprehensive Conceptual Framework and an Applied Safety Culture Assessment Instrument
Full text linkAn exponential amount of academic research has been dedicated to the safety culture concept, but still, no consensus has been reached on its definition and content. In general, safety culture research lacks an interdisciplinary approach. Furthermore, although the concept of safety culture is characterised by complexity and multifacetedness, the safety culture concept has been characterised by reductionism, where models and theories simplify the concept in order to better grasp it, leading to confined approaches. In this article, the multifacetedness of safety culture is acknowledged, and the topic is addressed from a safety science perspective, combining insights from multiple academic disciplines. An integrative and comprehensive conceptual framework to assess safety culture in organisations is developed, taking into account the limitations of existing models, as well as the needs of the work field. This conceptual framework is called the ‘Integrated Safety Culture Assessment’ (ISCA), where the ‘assessment’ refers to its practical usability. The practical rendition of ISCA can be used to map the safety culture of an organisation and to formulate recommendations in this regard, with the ultimate goal of bringing about a change towards a positive safety culture. The comprehensiveness of ISCA lies in the inclusion of technological factors, organisational or contextual factors and human factors interacting and interrelating with each other, and in considering both observable or objective safety-related aspects in an organisation, and non-observable or subjective safety-related aspects. When using ISCA, organisational safety culture is assessed in an integrative way by using a variety of research methods involving the entire organisation, and by taking into account the specific context of the organisation
Nudging as a crime prevention strategy: the use of nudges to improve cyclists’ locking behavior and reduce the opportunities for bicycle theft
No full textAs policy makers are developing new alternative strategies to prevent bicycle theft, a nudging approach could provide useful insights in this field. In the current study, two different nudges were implemented at a selection of bicycle parking facilities in the neighborhood of a Belgian university campus. To measure the effectiveness of the nudges, a multi-method approach was used with a combination of observations (n = 3963) and questionnaires (n = 197). The results showed that both nudges had a positive impact on cyclists’ locking behavior. Based on these findings, it can be concluded that nudging can be a rather cheap and easy way to improve secure behavior. However, concerns such as the limitations of increased awareness on behavior and the excessive focus on the victim need to be taken into account when implementing nudges in the field of security.Safety and Security Scienc
Saishin Toyohara shigai meisaizu /
No full textMap of Toyohara-shi (known as Vladimirovka (NQwLADÍMIROWKA) 1882-1905; Bsince 1946 known as Yuzhno-Sakhalinsk (NQ`VNO-sAHALÍNSK)), Bthe capital of the Japan's Karafuto prefecture 1905-1946. The city is now capital of the Russia's Sakhalin Oblast.; Issued in envelope cover.; Also available online http://nla.gov.au/nla.map-vn6490259. 880-05 Hokkaido Karafuto renraku tetsudo kotsu oyobi nidai kokuritsu koen annaizu (1:3,000,000).880-03 On the map : Toyohara shigai chiz
The role of education in the prevention of radicalization and violent extremism in developing countries
Full text linkAbstract: Only since the beginning of this century, the prevention of radicalization has become an important topic in debates about terrorism and sustainable development in developing countries. Research has shown that radicalized individuals are not uneducated, but have often completed secondary or tertiary education. Additionally, it became clear that some extremist groups consider the school environment as an attractive recruitment place. These findings led to a new approach where the education sector is considered as a prominent partner in preventing and combating the radicalization of young individuals. In this article, the potential limitations of the role of the education sector in developing countries are exposed. Based on previous research, three bottlenecks in the education sector were found: unequal access to education, poor quality of education and the relationship between education and employment. In order to strengthen the role of education for sustainable development in developing countries, it is recommended that equal access to education is improved, that schools invest in the creation of safe spaces for their students, that not only secondary but also primary and tertiary education are involved in policy strategies regarding radicalization, and that the job market is adjusted to the educational level of graduated students
- …
