bluuebunny/crossref_metadata_2025 huggingface dataset:
On convergence criteria for branched continued fraction
Authors: Antonova T.M.
Published: June 2020

The starting point of the present paper is a result by E.A. Boltarovych (1989) on convergence regions, dealing with branched continued fraction \[\sum_{i_1=1}^N\frac{a_{i(1)}}{1}{\atop+}\sum_{i_2=1}^N\frac{a_{i(2)}}{1}{\atop+}\ldots{\atop+}\sum_{i_n=1}^N\frac{a_{i(n)}}{1}{\atop+}\ldots,\] where $|a_{i(2n-1)}|\le\alpha/N,$ $i_p=\overline{1,N},$ $p=\overline{1,2n-1},$ $n\ge1,$ and for each multiindex $i(2n-1)$ there is a single index $j_{2n},$ $1\le j_{2n}\le N,$ such that $|a_{i(2n-1),j_{2n}}|\ge R,$ $i_p=\overline{1,N},$ $p=\overline{1,2n-1},$ $n\ge1,$ and $|a_{i(2n)}|\le r/(N-1),$ $i_{2n}\ne j_{2n},$ $i_p=\overline{1,N},$ $p=\overline{1,2n},$ $n\ge1,$ where $N>1$ and $\alpha,$ $r$ and $R$ are real numbers that satisfying certain conditions. In the present paper conditions for these regions are replaced by $\sum_{i_1=1}^N|a_{i(1)}|\le\alpha(1-\varepsilon),$ $\sum_{i_{2n+1}=1}^N|a_{i(2n+1)}|\le\alpha(1-\varepsilon),$ $i_p=\overline{1,N},$ $p=\overline{1,2n},$ $n\ge1,$ and for each multiindex $i(2n-1)$ there is a single index $j_{2n},$ $1\le j_{2n}\le N,$ such that $|a_{i(2n-1),j_{2n}}|\ge R$ and $\sum_{i_{2n}\in\{1,2,\ldots,N\}\backslash\{j_{2n}\}}|a_{i(2n)}|\le r,$ $i_p=\overline{1,N},$ $p=\overline{1,2n-1},$ $n\ge1,$ where $\varepsilon,$ $\alpha,$ $r$ and $R$ are real numbers that satisfying certain conditions, and better convergence speed estimates are obtained.
La utilidad de una concepción de seguridad nacional moderna y dinámica, en la lucha contra el crimen organizado en América Latina
Authors: Bartolomé Mariano César
Published: June 2020

En el actual panorama de seguridad latinoamericano adquiere particular relevancia la criminalidad organizada, con un nítido correlato de violencia. Para enfrentar con eficacia esta situación, las naciones de la región han realizado importantes esfuerzos, que hasta hoy no ha arrojado los resultados esperados, de acuerdo a la propia Organización de Estados Americanos.El objetivo del presente trabajo consiste en plantear la utilidad que puede reportar un moderno enfoque de seguridad nacional, amplio y abarcativo, para realizar un abordaje integral al flagelo de la criminalidad en la región. Ese enfoque debe trascender las perspectivas tradicionales de seguridad pública, que enfatizan en la prevención y represión del delito, para incluir además lecturas multicausales más amplias, propias de la seguridad ciudadana. El punto de vista de la seguridad ciudadana permite detectar tres factores de clara incidencia directa en la difusión y profundización de la criminalidad organizada en América Latina: la corrupción, la impunidad y la fragilidad estatal con insuficiente gobernabilidad.Nuestro análisis sostiene que en América Latina es posible adoptar una concepción de seguridad nacional moderna y dinámica, lejos de la controvertida Doctrina de la Seguridad Nacional de la Guerra Fría. Esa concepción debe reconocer la heterogeneidad de amenazas y riesgos contemporáneos, y que combine seguridad pública y seguridad ciudadana en la lucha contra el crimen organizado. Argentina, Guatemala y México son ejemplos de la adopción de modernos enfoques de este tipo, perfectamente compatibles con la vigencia del sistema democrático y el respeto a los derechos humanos.El artículo se estructura en una introducción, un desarrollo dividido en tres partes, y unas breves conclusiones. En el desarrollo, primero se revisarán algunas cuestiones atinentes a la criminalidad latinoamericana, identificando tres elementos que inciden en su crecimiento y expansión, y que son abordables desde una perspectiva de seguridad ciudadana. Luego se describirán los límites y contenidos del moderno concepto seguridad nacional, señalando que sus alcances pueden incluir el combate al crimen organizado. En tercer lugar, identificaremos y describiremos someramente tres casos de aplicación en América Latina de una concepción moderna de seguridad nacional que incluyen, dentro de sus áreas de incumbencia, a la criminalidad organizada.
La gobernanza regional de la cooperación Sur-Sur en América Latina
Authors: Ruiz-Camacho Paula Ximena
Published: June 2020

La cooperación Sur-Sur se ha consolidado como una modalidad complementaria a la tradicional cooperación Norte-Sur que, en la práctica, se ha materializado como un instrumento para el intercambio de ideas, políticas y experiencias, que se ejecuta entre países en desarrollo que tienen, o creen tener, elementos políticos, históricos y socioeconómicos afines. Sus orígenes se remontan a la década de los cincuenta, y desde entonces, la estructura ideológica que le ha dado forma ha estado influenciada por ideas y hechos que se interrelacionan a partir de distintas narrativas construidas por los estados, subrayando intereses comunes sobre el lugar que ocupan dentro de la arquitectura de la cooperación al desarrollo. A lo largo del siglo XXI, dicha modalidad ha ido ganando mayores espacios de concertación y negociación como un instrumento político de los países en desarrollo que se sustenta en los principios de horizontalidad, solidaridad, reciprocidad e independencia. Desde un enfoque regional, América Latina, por ejemplo, ha favorecido la creación de instrumentos técnicos que, desde la conceptualización hasta el registro de datos, han llevado a la creación de estructuras normativas para la ejecución de la cooperación Sur-Sur. En esa línea argumentativa, desde un enfoque social constructivista de difusión de ideas, normas y prácticas, este artículo analiza de manera descriptiva y explicativa cómo la región ha fortalecido la práctica de la cooperación Sur-Sur a partir de la identificación de problemáticas comunes y discursos encaminados a definirla desde las estructuras ideacionales. El objetivo de este artículo es entender el proceso de formación de la gobernanza regional de la cooperación Sur-Sur en América Latina, para lo cual, se analiza el rol de la Secretaria General Iberoamericana desde cuya institucionalidad, los países de la región fortalecen la difusión de prácticas e ideas que podrían significar avances para la construcción de una gobernanza global de la cooperación Sur-Sur.
Protection of Socio-economic Rights under the ECHR
Authors: Milašiūtė Vygantė
Published: June 2020

The article examines to what extent and how the protection of socio-economic rights can be and is actually effected under the ECHR. This is done taking into account the fact that the protection of such rights is not a major objective of the ECHR but, in view of the indivisibility of human rights, the realisation of some socio-economic rights is necessary for the realisation of the ECHR rights.
European Mediation and Indigenous Mediation
Authors: Brandão Bárrios Luísa
Published: June 2020

The article investigates the European and Indigenous mediation and its different circumstances. Mediation is one of a variety of procedures to solve a conflict; it is based on the voluntary participation of the parties and it is a procedure, in which an intermediary without adjudicatory powers (the mediator) systematically facilitates communication between the parties with the aim of enabling the parties themselves to take responsibility for resolving their dispute.
Studi Kenabian Muhammad Perspektif Michael Cook
Authors: Alkawy Mohamad Baihaqi
Published: June 2020

Muhammad’s prophetic studies have been carried out through various approaches, Michael Cook chose a revisionist approach to seek to explore the history of prophecy through written evidence. In his view, Muhammad’s biography must be examined in more detail based on the evidence obtained to uncover the mystical veils in history. Cook’s criticism of the biographers of Muhammad, made him have to work hard to look at and re-examine the texts of the Quran more closely. This Article will explain the result of Cook’s studies about Muhammad’s success in shifting polytheism to monotheism. In addition, it shows the success of Muhammad as a political actor.
Effect of different training modes of strength exercises on a student’s body
Authors: Fedyakin Alexander A. , Kortava Zhanna G. , Fedyakina Lidia K. , Zaplatina Natalia Yu.
Published: June 2020

Background and Study Aim. Scientific-methodical literature underlined the importance of improving the effectiveness of physical education’s tools and methods during the scheduled university lessons. Scientists point out the necessity to take into account every factor determining the training effect of lessons with strength exercises. The immediate training effect can be determined by measuring the heart rate during different modes of strength exercises and during recovery. The aim of this study is to analyse the strength exercises’ immediate training effect on a student’s body in the static mode and in the isotonic mode.
Material and Methods.  In the study participated 47 freshman male students of the Sochi State University (Russia). The study took place in September-December 2019. Heart rate was measured with Sport Testers POLAR RS-400 during strength exercises and during recovery. The results were analysed in the computer programme SPSS Statistics v22.0. Statistical significance of the results was defined using non-parametric Wilcoxon test. Heart rate was analysed during four types of plank positions in static and isotonic modes.
Results: The study determined the effect of different training modes of strength exercises on a student’s body. The immediate training effect of doing the bodyweight strength exercises in the isotonic mode compared to the static mode is characterised by a higher maximum heart rate at the end of doing the exercise (р<0,05); a higher average heart rate during the exercise and during rest until the next exercise (р<0,05); a higher combined heart rate (р<0,05).
Conclusion: The isotonic mode of the bodyweight strength exercises has a more prominent training effect than the static mode due to the specific nature of muscle contractions. Due to analysed heart rate values, the authors recommend taking into account the individual level of every student’s physical fitness.
MAWĀRID ‘ASĀ FĪ AL QURĀN AL-KARĪM
Authors: Musthofa Qoribulloh Babakr
Published: June 2020

Tujuan dari penelitian ini adalah untuk mendeskripsikan ayat-ayat yang mengandung kata (‘asā) dalam Al-Qur’an, mengkajinya secara kaidah nahwiyah, mengklarifikasi makna semantik (‘asā) dalam Alquran Suci. Metode yang digunakan dalam penelitian ini adalah metode deskriptif. Hasil penelitian menunjukkan bahwa: 1) jumlah tempat kata ‘asā’ dalam Al-Qur’an sebanyak tiga puluh ayat;  2) jumlah ayat yang mengandung kata ‘asā’ dalam Al-Qur’an disebutkan dua puluh delapan ayat; 3) kata ‘asā’ lebih tepat disebut sebagai fi’il, yaitu bagian dari fi’il nāqish yang beramal seperti amal “kāna”; 4) Kata ‘asā’ bisa digunakan secara sempurna dengan fā’il saja sebagai pengganti khabar, ataupun sebagai fi’il nāqish yag menyembunyikan isimnya; 5) kata ‘asā’ dalam Al-Qur’an memiliki tiga makna, yaitu bermakna wajib, bermakna harapan dan bermakna belaskasihan. Karena itu, peneliti selanjutnya diharapkan dapat meneruskan penelitian dengan af’āl al muqārabah dalam Al-Qur’an seperti fi’il “kāda” . demikian pula bagi mahasiswa agar mempelajari fi’il nawāsikh dalam Al-Qur’an.
ISTIKHDĀM NAMŪDZAJ AL-TA’LĪM ‘ALĀ ASĀS HILLI AL-MUSYKILĀT FĪ TA’LĪM AL-NAHW AL-‘ARABĪ LI TARQIYAH NATĪJAH TA’LĪM AL-THALABAH FĪHI
Authors: Sanah Siti , Ghazali Dede Ahmad , Hafair Ahmad
Published: June 2020

Penelitian ini bertolak dari permasalahan pembelajaran nahwu  yaitu rendahnya hasil belajar santri kelas ibtidai Pondok Pesantren Majma’ul Anhar. Maka dari itu, seorang guru hendaknya memilih model pembelajaran yang sesuai untuk meningkatkan hasil belajar siswa. Adapun tujuan penelitian ini untuk mengetahui hasil belajar santri sebelum dan sesudah menggunakan model Problem Based Learning (PBL), serta untuk mengetahui peningkatan hasil belajar santri. Adapun metode penelitian yang digunakan adalah metode Quasi-Eksperimen dengan one group pre-test post-test design. Teknik pengumpulan data yang digunakan adalah teknik seperti wawancara, observasi, tes, dan studi kepustakaan. Penggunaan model Problem Based Learning dalam pembelajaran nahw terbukti meningkatkan hasil belajar santri, sebagaimana ditunjukan oleh nilai n-gain dengan hasil 0,34 yang berada pada taraf sedang.
ISTIKHDĀM DAWĀIR AL-BITHĀQĀH FĪ TA’LĪM AL-LUGHAH AL-‘ARABIYYAH LI MĀDAH AL-TARKĪB LI TARQIYATI TAHSHĪL AL-TALĀMIDZ AL-DIRĀSI FĪHI
Authors: Syafe'i Isop , Fauziah Neng Nada Putri
Published: June 2020

Berdasarkan Hasil Belajar Siswa dalam pembelajaran Bahasa Arab Materi Tarkib di MA Al-Istiqomah Cijerah Bandung yaitu rendah. Dan faktor yang menyebabkan rendahnya itu adalah latar belakang siswa, minat dan bakat siswa, motivasi siswa. Oleh karena itu, guru membutuhkan media yang tepat untuk mencapai tujuan utama dalam pembelajaran Bahasa Arab Materi Tarkib dengan media Circular Card. Tujuan penelitian ini adalah untuk mengetahui hasil belajar siswa pada pembelajaran bahasa Arab materi Tarkib sebelum dan sesudah menggunakan media circular card, serta mengetahui peningkatan hasil belajar siswa. Metode yang digunakan pada penelitian ini adalah metode eksperimen model pretest dan post test design. Hasil dari penelitian adalah bahwa hasil belajar siswa pada pembelajaran Bahasa Arab Materi Tarkib sebelum menggunakan media circular card menunjukkan pada kategori nilai 64. Hasil belajar siswa setelah menggunakan media circular card menunjukkan pada kategori nilai 81. Serta peningkatan hasil belajar siswa pada pembelajaran Bahasa Arab Materi Tarkib menunjukkan pada kategori 0,66 atau 66%.
Capital Exchange between Islamic Boarding Schools and Political Parties in the 2019 Election
Authors: Kholifah Siti
Published: June 2020

This study examines the social practices of Islamic boarding schools in Jombang in the 2019 elections. It aims to analyze the role and capital exchange between Islamic boarding schools in Jombang and political parties. This study is important because the intersection of Islamic boarding schools and politics has been going on since colonial times until now. The political dynamics of Islamic boarding schools cannot be separated from NU because several NU Kiai are in the vortex of local and national politics. In the 2019 presidential election, a Kiai of NU named Kiai Ma’ruf Amin ran as Jokowi’s partner to be a vice president. As a place for the establishment of NU, Islamic boarding schools in Jombang have a magnet in gaining votes both in the legislative and presidential elections in 2019. By using Pierre ’Bourdieu’s theory as an analytical tool, this research conducted a case study approach. Data collection techniques carried out through interviews, observation, and documentation. The informants are determined purposively. The results of this study indicate that the exchange of capital between Islamic boarding schools and political parties is dominated by symbolic capital exchanges of Islamic boarding schools with the social capital of political elites and political parties. The blue bloodline of Islamic boarding schools and seniority of a Kiai or Nyai have an essential role in determining the reproductive strategy and capital exchange with political parties. Also, the dominance of social practices carried out in Islamic boarding schools. The power of symbolic capital and social capital of NU Islamic boarding school became a tool for conducting bargaining positions with elite political parties, including presidential and vice-presidential candidates. In the end, the capital exchange between Islamic boarding schools and political parties became obvious in getting votes in the 2019 elections.
Impacts of pollution discharges from Dinh Vu industrial zone on water quality in the Hai Phong coastal area
Authors: Vinh Vu Duy , Hai Nguyen Minh , Khanh Do Gia
Published: June 2020

The hydrodynamic and water quality models (the Delft3D model) were established based on the measured data and the estimated pollution discharges from Dinh Vu industrial zones to Nam Trieu estuary. With seven separate simulation scenarios, the results show that in case of increased wastewater with the control of pollution discharge (water and concentration), the impact of pollution is only limited to a small area around the discharge point. Their influences on water quality in other areas in Nam Trieu estuary are quite small. Meanwhile, in case of environmental risk, a strongly increasing pollution load would cause the significantly increasing pollutant concentration in this area, they have almost exceeded the value in the National Technical Regulation on surface water quality (QCVN 10-MT:2015/BTNMT), such as NH4, COD, and BOD. Dissolved oxygen in the water would also decrease significantly. The spatial influence extends from the discharge point to Nam Trieu estuary, inside Cam, Bach Dang rivers, and Cat Hai coastal area.
Reasons and effects of the implementation of corporate social responsibility principles into company management
Authors: Giemza Maryla
Published: June 2020

In the last decade, governments and stakeholders’ expectations of companies regarding responsible business behaviour have increased. Profitability and efficiency cease to be the only key features that the company wants to be known for. The social context of business and its’ contribution to sustainable development, regardless of legal status, size or industry, is becoming increasingly important. The aim of the article is to analyze the motives and benefits of implementing social responsibility into the management practice of companies. To achieve this goal, an analysis and synthesis of the subject literature as well as statistical secondary data analysis were carried out. The conclusions imply that the motives for implementing the principles of social responsibility are various, but they bring benefits – internal and external.
Problems of rural territories as a threat to the balance of spatial development of the country
Authors: Gataullin Rinat
Published: June 2020

The article defines rural territories as a system of interrelated economic, social and environmental elements in which agricultural production, a specific type of settlement and the way of life of the population play a systematizing role. The article deals with the "shocks" that the Russian village experienced in the XX century and their results in the form of the collapse of the rural economy, the features of employment and income generation, and the related economic and social problems of the country.
The lack of balance in the development of rural areas poses a threat not only to their sustainability, but also to the entire country as a whole in the form of reduced food security, reduced use of existing potential, including land.
It also shows a growing imbalance in the social development of cities and villages: in wages, in the functioning of social infrastructure, in training and employment.
The balance of spatial development is considered as a dynamic process aimed at ensuring its sustainability, when the entire existing potential of the village is used for the benefit of society.
The main link that does not allow for the balanced development of rural areas is the existence of "high prices" in the exchange between the city and the village. The main functions in ensuring a balanced development of rural territories by management levels are shown.
As the main lever in overcoming existing disparities in the development of cities and villages, the system of targeted support for depressed territories is considered in accordance with the following principles: cost self-sufficiency, competitiveness of planned products and increasing the technical level of production.
Bricolagem na criação e trajetória de um circo contemporâneo
Authors: Machado Hilka Pelizza Vier
Published: June 2020

Resumo A bricolagem é uma abordagem que considera que a ação resulta de uma combinação de recursos para novos propósitos, com recursos disponíveis e escassos (Fisher, 2012). O objetivo desta pesquisa foi descrever e analisar o surgimento e a trajetória de um circo contemporâneo como um processo compreendido por meio da abordagem da bricolagem. O tipo de pesquisa foi o estudo qualitativo e exploratório, na forma de estudo de caso. Foram utilizadas entrevistas e dados secundários. Os dados foram codificados com auxílio do software N vivo 9. A codificação resultou em cinco temáticas: o nascimento do circo - making do; limitações impostas pelo ambiente; a bricolagem network; improvisação e mobilização; e reputação. A principal contribuição teórica foi utilizar a abordagem da bricolagem para explicar o surgimento e a trajetória de um circo contemporâneo, abordando o processo a partir de atores, ações e percepções.
HISTORY OF MATHEMATICS EDUCATION IN PRIMARY SCHOOL AND IN TEACHER TRAINING IN BRAZIL
Authors: Valente Wagner Rodrigues , Silva Maria Célia Leme da
Published: June 2020

Abstract This article discusses results from research developed on the transformations in mathematics teaching in primary school and the mathematics in teacher training from the 19th century to the mid-20th century in Brazil. We have analyzed the understanding of the relationship between the mathematical disciplinary field and pedagogy in order to confirm the theoretical hypothesis that the interactions between the two fields produce mathematics of different natures, which are interconnected.
Machine Number Sense: A Dataset of Visual Arithmetic Problems for Abstract and Relational Reasoning
Authors: Zhang Wenhe , Zhang Chi , Zhu Yixin , Zhu Song-Chun
Published: June 2020

As a comprehensive indicator of mathematical thinking and intelligence, the number sense (Dehaene 2011) bridges the induction of symbolic concepts and the competence of problem-solving. To endow such a crucial cognitive ability to machine intelligence, we propose a dataset, Machine Number Sense (MNS), consisting of visual arithmetic problems automatically generated using a grammar model—And-Or Graph (AOG). These visual arithmetic problems are in the form of geometric figures: each problem has a set of geometric shapes as its context and embedded number symbols. Solving such problems is not trivial; the machine not only has to recognize the number, but also to interpret the number with its contexts, shapes, and relations (e.g., symmetry) together with proper operations. We benchmark the MNS dataset using four predominant neural network models as baselines in this visual reasoning task. Comprehensive experiments show that current neural-network-based models still struggle to understand number concepts and relational operations. We show that a simple brute-force search algorithm could work out some of the problems without context information. Crucially, taking geometric context into account by an additional perception module would provide a sharp performance gain with fewer search steps. Altogether, we call for attention in fusing the classic search-based algorithms with modern neural networks to discover the essential number concepts in future research.
To Signal or Not To Signal: Exploiting Uncertain Real-Time Information in Signaling Games for Security and Sustainability
Authors: Bondi Elizabeth , Oh Hoon , Xu Haifeng , Fang Fei , Dilkina Bistra , Tambe Milind
Published: June 2020

Motivated by real-world deployment of drones for conservation, this paper advances the state-of-the-art in security games with signaling. The well-known defender-attacker security games framework can help in planning for such strategic deployments of sensors and human patrollers, and warning signals to ward off adversaries. However, we show that defenders can suffer significant losses when ignoring real-world uncertainties despite carefully planned security game strategies with signaling. In fact, defenders may perform worse than forgoing drones completely in this case. We address this shortcoming by proposing a novel game model that integrates signaling and sensor uncertainty; perhaps surprisingly, we show that defenders can still perform well via a signaling strategy that exploits uncertain real-time information. For example, even in the presence of uncertainty, the defender still has an informational advantage in knowing that she has or has not actually detected the attacker; and she can design a signaling scheme to “mislead” the attacker who is uncertain as to whether he has been detected. We provide theoretical results, a novel algorithm, scale-up techniques, and experimental results from simulation based on our ongoing deployment of a conservation drone system in South Africa.
Deep Unsupervised Binary Coding Networks for Multivariate Time Series Retrieval
Authors: Zhu Dixian , Song Dongjin , Chen Yuncong , Lumezanu Cristian , Cheng Wei , Zong Bo , Ni Jingchao , Mizoguchi Takehiko , Yang Tianbao , Chen Haifeng
Published: June 2020

Multivariate time series data are becoming increasingly ubiquitous in varies real-world applications such as smart city, power plant monitoring, wearable devices, etc. Given the current time series segment, how to retrieve similar segments within the historical data in an efficient and effective manner is becoming increasingly important. As it can facilitate underlying applications such as system status identification, anomaly detection, etc. Despite the fact that various binary coding techniques can be applied to this task, few of them are specially designed for multivariate time series data in an unsupervised setting. To this end, we present Deep Unsupervised Binary Coding Networks (DUBCNs) to perform multivariate time series retrieval. DUBCNs employ the Long Short-Term Memory (LSTM) encoder-decoder framework to capture the temporal dynamics within the input segment and consist of three key components, i.e., a temporal encoding mechanism to capture the temporal order of different segments within a mini-batch, a clustering loss on the hidden feature space to capture the hidden feature structure, and an adversarial loss based upon Generative Adversarial Networks (GANs) to enhance the generalization capability of the generated binary codes. Thoroughly empirical studies on three public datasets demonstrated that the proposed DUBCNs can outperform state-of-the-art unsupervised binary coding techniques.
Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
Authors: Ding Jian-Ya , Zhang Chao , Shen Lei , Li Shengyin , Wang Bing , Xu Yinghui , Song Le
Published: June 2020

Mixed Integer Programming (MIP) is one of the most widely used modeling techniques for combinatorial optimization problems. In many applications, a similar MIP model is solved on a regular basis, maintaining remarkable similarities in model structures and solution appearances but differing in formulation coefficients. This offers the opportunity for machine learning methods to explore the correlations between model structures and the resulting solution values. To address this issue, we propose to represent a MIP instance using a tripartite graph, based on which a Graph Convolutional Network (GCN) is constructed to predict solution values for binary variables. The predicted solutions are used to generate a local branching type cut which can be either treated as a global (invalid) inequality in the formulation resulting in a heuristic approach to solve the MIP, or as a root branching rule resulting in an exact approach. Computational evaluations on 8 distinct types of MIP problems show that the proposed framework improves the primal solution finding performance significantly on a state-of-the-art open-source MIP solver.
Justifying All Differences Using Pseudo-Boolean Reasoning
Authors: Elffers Jan , Gocht Stephan , McCreesh Ciaran , Nordström Jakob
Published: June 2020

Constraint programming solvers support rich global constraints and propagators, which make them both powerful and hard to debug. In the Boolean satisfiability community, proof-logging is the standard solution for generating trustworthy outputs, and this has become key to the social acceptability of computer-generated proofs. However, reusing this technology for constraint programming requires either much weaker propagation, or an impractical blowup in proof length. This paper demonstrates that simple, clean, and efficient proof logging is still possible for the all-different constraint, through pseudo-Boolean reasoning. We explain how such proofs can be expressed and verified mechanistically, describe an implementation, and discuss the broader implications for proof logging in constraint programming.
A Cardinal Improvement to Pseudo-Boolean Solving
Authors: Elffers Jan , Nordstrm Jakob
Published: June 2020

Pseudo-Boolean solvers hold out the theoretical potential of exponential improvements over conflict-driven clause learning (CDCL) SAT solvers, but in practice perform very poorly if the input is given in the standard conjunctive normal form (CNF) format. We present a technique to remedy this problem by recovering cardinality constraints from CNF on the fly during search. This is done by collecting potential building blocks of cardinality constraints during propagation and combining these blocks during conflict analysis. Our implementation has a non-negligible but manageable overhead when detection is not successful, and yields significant gains for some SAT competition and crafted benchmarks for which pseudo-Boolean reasoning is stronger than CDCL. It also boosts performance for some native pseudo-Boolean formulas where this approach helps to improve learned constraints.
Solving Set Cover and Dominating Set via Maximum Satisfiability
Authors: Lei Zhendong , Cai Shaowei
Published: June 2020

The Set Covering Problem (SCP) and Dominating Set Problem (DSP) are NP-hard and have many real world applications. SCP and DSP can be encoded into Maximum Satisfiability (MaxSAT) naturally and the resulting instances share a special structure. In this paper, we develop an efficient local search solver for MaxSAT instances of this kind. Our algorithm contains three phrase: construction, local search and recovery. In construction phrase, we simplify the instance by three reduction rules and construct an initial solution by a greedy heuristic. The initial solution is improved during the local search phrase, which exploits the feature of such instances in the scoring function and the variable selection heuristic. Finally, the corresponding solution of original instance is recovered in the recovery phrase. Experiment results on a broad range of large scale instances of SCP and DSP show that our algorithm significantly outperforms state of the art solvers for SCP, DSP and MaxSAT.
An Effective Hard Thresholding Method Based on Stochastic Variance Reduction for Nonconvex Sparse Learning
Authors: Liang Guannan , Tong Qianqian , Zhu Chunjiang , Bi Jinbo
Published: June 2020

We propose a hard thresholding method based on stochastically controlled stochastic gradients (SCSG-HT) to solve a family of sparsity-constrained empirical risk minimization problems. The SCSG-HT uses batch gradients where batch size is pre-determined by the desirable precision tolerance rather than full gradients to reduce the variance in stochastic gradients. It also employs the geometric distribution to determine the number of loops per epoch. We prove that, similar to the latest methods based on stochastic gradient descent or stochastic variance reduction methods, SCSG-HT enjoys a linear convergence rate. However, SCSG-HT now has a strong guarantee to recover the optimal sparse estimator. The computational complexity of SCSG-HT is independent of sample size n when n is larger than 1/ε, which enhances the scalability to massive-scale problems. Empirical results demonstrate that SCSG-HT outperforms several competitors and decreases the objective value the most with the same computational costs.
Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms
Authors: Sahai Tuhin , Mishra Anurag , Pasini Jose Miguel , Jha Susmit
Published: June 2020

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
Hard Examples for Common Variable Decision Heuristics
Authors: Vinyals Marc
Published: June 2020

The CDCL algorithm for SAT is equivalent to the resolution proof system under a few assumptions, one of them being an optimal non-deterministic procedure for choosing the next variable to branch on. In practice this task is left to a variable decision heuristic, and since the so-called VSIDS decision heuristic is considered an integral part of CDCL, whether CDCL with a VSIDS-like heuristic is also equivalent to resolution remained a significant open question.We give a negative answer by building a family of formulas that have resolution proofs of polynomial size but require exponential time to decide in CDCL with common heuristics such as VMTF, CHB, and certain implementations of VSIDS and LRB.
Explaining Propagators for String Edit Distance Constraints
Authors: Winter Felix , Musliu Nysret , Stuckey Peter
Published: June 2020

The computation of string similarity measures has been thoroughly studied in the scientific literature and has applications in a wide variety of different areas. One of the most widely used measures is the so called string edit distance which captures the number of required edit operations to transform a string into another given string. Although polynomial time algorithms are known for calculating the edit distance between two strings, there also exist NP-hard problems from practical applications like scheduling or computational biology that constrain the minimum edit distance between arrays of decision variables. In this work, we propose a novel global constraint to formulate restrictions on the minimum edit distance for such problems. Furthermore, we describe a propagation algorithm and investigate an explanation strategy for an edit distance constraint propagator that can be incorporated into state of the art lazy clause generation solvers. Experimental results show that the proposed propagator is able to significantly improve the performance of existing exact methods regarding solution quality and computation speed for benchmark problems from the literature.
Draft and Edit: Automatic Storytelling Through Multi-Pass Hierarchical Conditional Variational Autoencoder
Authors: Yu Meng-Hsuan , Li Juntao , Liu Danyang , Zhao Dongyan , Yan Rui , Tang Bo , Zhang Haisong
Published: June 2020

Automatic Storytelling has consistently been a challenging area in the field of natural language processing. Despite considerable achievements have been made, the gap between automatically generated stories and human-written stories is still significant. Moreover, the limitations of existing automatic storytelling methods are obvious, e.g., the consistency of content, wording diversity. In this paper, we proposed a multi-pass hierarchical conditional variational autoencoder model to overcome the challenges and limitations in existing automatic storytelling models. While the conditional variational autoencoder (CVAE) model has been employed to generate diversified content, the hierarchical structure and multi-pass editing scheme allow the story to create more consistent content. We conduct extensive experiments on the ROCStories Dataset. The results verified the validity and effectiveness of our proposed model and yields substantial improvement over the existing state-of-the-art approaches.
Distance-Based Equilibria in Normal-Form Games
Authors: Acar Erman , Meir Reshef
Published: June 2020

We propose a simple uncertainty modification for the agent model in normal-form games; at any given strategy profile, the agent can access only a set of “possible profiles” that are within a certain distance from the actual action profile. We investigate the various instantiations in which the agent chooses her strategy using well-known rationales e.g., considering the worst case, or trying to minimize the regret, to cope with such uncertainty. Any such modification in the behavioral model naturally induces a corresponding notion of equilibrium; a distance-based equilibrium. We characterize the relationships between the various equilibria, and also their connections to well-known existing solution concepts such as Trembling-hand perfection. Furthermore, we deliver existence results, and show that for some class of games, such solution concepts can actually lead to better outcomes.
Swap Stability in Schelling Games on Graphs
Authors: Agarwal Aishwarya , Elkind Edith , Gan Jiarui , Voudouris Alexandros
Published: June 2020

We study a recently introduced class of strategic games that is motivated by and generalizes Schelling's well-known residential segregation model. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either occupies a node of the graph and never moves away or aims to maximize the fraction of her neighbors who are of her own type. We consider a variant of this model that we call swap Schelling games, where the number of agents is equal to the number of nodes of the graph, and agents may swap positions with other agents to increase their utility. We study the existence, computational complexity and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective.
The Impact of Selfishness in Hypergraph Hedonic Games
Authors: Aloisio Alessandro , Flammini Michele , Vinci Cosimo
Published: June 2020

We consider a class of coalition formation games that can be succinctly represented by means of hypergraphs and properly generalizes symmetric additively separable hedonic games. More precisely, an instance of hypegraph hedonic game consists of a weighted hypergraph, in which each agent is associated to a distinct node and her utility for being in a given coalition is equal to the sum of the weights of all the hyperedges included in the coalition. We study the performance of stable outcomes in such games, investigating the degradation of their social welfare under two different metrics, the k-Nash price of anarchy and k-core price of anarchy, where k is the maximum size of a deviating coalition. Such prices are defined as the worst-case ratio between the optimal social welfare and the social welfare obtained when the agents reach an outcome satisfying the respective stability criteria. We provide asymptotically tight upper and lower bounds on the values of these metrics for several classes of hypergraph hedonic games, parametrized according to the integer k, the hypergraph arity r and the number of agents n. Furthermore, we show that the problem of computing the exact value of such prices for a given instance is computationally hard, even in case of non-negative hyperedge weights.
Adapting Stable Matchings to Evolving Preferences
Authors: Bredereck Robert , Chen Jiehua , Knop Dušan , Luo Junjie , Niedermeier Rolf
Published: June 2020

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.
Approval-Based Apportionment
Authors: Brill Markus , Gölz Paul , Peters Dominik , Schmidt-Kraepelin Ulrike , Wilker Kai
Published: June 2020

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.
Preventing Arbitrage from Collusion When Eliciting Probabilities
Authors: Freeman Rupert , Pennock David M. , Peters Dominik , Waggoner Bo
Published: June 2020

We consider the design of mechanisms to elicit probabilistic forecasts when agents are strategic and may collude with one another. Chun and Shachter (2011) have shown that when agents may form coalitions, many known mechanisms for elicitation permit arbitrage, allowing the coalition members to guarantee themselves higher payments by misreporting their beliefs. We consider two approaches to protect against colluding agents. First, we present a novel strictly proper mechanism that does not admit arbitrage provided that the reports of the agents are bounded away from 0 and 1, a common assumption in many settings. Second, we discover strictly arbitrage-free mechanisms that satisfy an intermediate guarantee between weak and strict properness.
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
Authors: Goldberg Paul W. , Hollender Alexandros , Suksompong Warut
Published: June 2020

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results strengthening those from prior work.
An Analysis Framework for Metric Voting based on LP Duality
Authors: Kempe David
Published: June 2020

Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by non-decreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule's choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule's distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee distortion at most 5; a very recent result gave a rule with distortion 2 + √5 ≈ 4.236.We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we show that the Ranked Pairs and Schulze rules have distortion Θ(√n). Second, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent 2 + √5 guarantee. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.
Limitations of Incentive Compatibility on Discrete Type Spaces
Authors: Lundy Taylor , Fu Hu
Published: June 2020

In the design of incentive compatible mechanisms, a common approach is to enforce incentive compatibility as constraints in programs that optimize over feasible mechanisms. Such constraints are often imposed on sparsified representations of the type spaces, such as their discretizations or samples, in order for the program to be manageable. In this work, we explore limitations of this approach, by studying whether all dominant strategy incentive compatible mechanisms on a set T of discrete types can be extended to the convex hull of T.Dobzinski, Fu and Kleinberg (2015) answered the question affirmatively for all settings where types are single dimensional. It is not difficult to show that the same holds when the set of feasible outcomes is downward closed. In this work we show that the question has a negative answer for certain non-downward-closed settings with multi-dimensional types. This result should call for caution in the use of the said approach to enforcing incentive compatibility beyond single-dimensional preferences and downward closed feasible outcomes.
Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games
Authors: Nakamura Kengo , Sakaue Shinsaku , Yasuda Norihito
Published: June 2020

Computation of equilibria for congestion games has been an important research subject. In many realistic scenarios, each strategy of congestion games is given by a combination of elements that satisfies certain constraints; such games are called combinatorial congestion games. For example, given a road network with some toll roads, each strategy of routing games is a path (a combination of edges) whose total toll satisfies a certain budget constraint. Generally, given a ground set of n elements, the set of all such strategies, called the strategy set, can be large exponentially in n, and it often has complicated structures; these issues make equilibrium computation very hard. In this paper, we propose a practical algorithm for such hard equilibrium computation problems. We use data structures, called zero-suppressed binary decision diagrams (ZDDs), to compactly represent strategy sets, and we develop a Frank–Wolfe-style iterative equilibrium computation algorithm whose per-iteration complexity is linear in the size of the ZDD representation. We prove that an ϵ-approximate Wardrop equilibrium can be computed in O(poly(n)/ϵ) iterations, and we improve the result to O(poly(n) log ϵ−1) for some special cases. Experiments confirm the practical utility of our method.