229 research outputs found
SDP-based Max-2-Sat Decomposition
No full textThe Max-Sat problem has been intensively studied during the past few decades. Semi-definite programming based approximation algorithms provide good approximation ratios and polynomial runtime solutions to this problem. Unfortunately the high degree of their polynomial runtime prevents their application to problems with a large number of variables. We've investigated the possibility of decomposing Max-Sat problems to reduce the number of variables in the problems supplied to SDP solvers. We've considered several forms of decomposition and evaluated these empirically. The methods we investigated were able to approach the lower bounds of SDP within 2% but do not provide performance guarantees and cannot compete with conventional local search methods.AlgorithmicsSoftware TechnologyElectrical Engineering, Mathematics and Computer Scienc
Exactness criteria for SDP-relaxations of quadratic extremum problems
No full textИсследованы условия получения точных решений квадратичных экстремальных задач общего вида с помощью SDP-релаксаций. На основе известных результатов относительно точности двойственных оценок (лагранжевых релаксаций) и их взаимосвязи с SDP-релаксациями сформулирован ряд условий, при которых оптимальные значения целевых функций квадратичной экстремальной задачи и ее SDP-релаксации равны.Досліджено умови отримання точних розв’язків квадратичних екстремальних задач загального вигляду за допомогою SDP-релаксацій. На основі відомих результатів стосовно точності двоїстих оцінок (лагранжевих релаксацій) і їхнього взаємозв’язку з SDP-релаксаціями сформульовано ряд умов, при яких оптимальні значення цільових функцій квадратичної екстремальної задачі та її SDP-релаксації рівні.The author analyzes the conditions of obtaining exact solutions to quadratic extremum problems of general type by using SDP-relaxations. Based on the known results for exactness of dual bounds (lagrangian relaxations) and their relationship with SDP-relaxations, several conditions are formulated, under which the values of optimal objective function of the quadratic extremal problem and its SDP-relaxation are equal
Open SDP
No full textThe original SDP 2014 and 2015 data collections were made available under task-specific ‘evaluation’ licenses to registered SemEval participants. In mid-2016, all original data has been bundled with system submissions, supporting software, an additional SDP-style collection of semantic dependency graphs, and additional background material (from which some of the SDP target representations were derived) for release through the Linguistic Data Consortium (with LDC catalogue number LDC2016 T10).
One of the four English target representations (viz. DM) and the entire Czech data (in the PSD target representation) are not derivative of LDC-licensed annotations and, thus, can be made available for direct download (Open SDP; version 1.1; April 2016) under a more permissive licensing scheme, viz. the Creative Common Attribution-NonCommercial-ShareAlike license. This package also includes some ‘richer’ meaning representations from which the English bi-lexical DM graphs derive, viz. scope-underspecified logical forms and more abstract, non-lexicalized ‘semantic networks’. The latter of these are formally (if not linguistically) similar to Abstract Meaning Representation (AMR) and are available in a range of serializations, including in AMR-like syntax.
Please use the following bibliographic reference for the SDP 2016 data:
@string{C:LREC = {{I}nternational {C}onference on
{L}anguage {R}esources and {E}valuation}}
@string{LREC:16 = {Proceedings of the 10th } # C:LREC}
@string{L:LREC:16 = {Portoro\v{z}, Slovenia}}
@inproceedings{Oep:Kuh:Miy:16,
author = {Oepen, Stephan and Kuhlmann, Marco and Miyao, Yusuke
and Zeman, Daniel and Cinkov{\'a}, Silvie
and Flickinger, Dan and Haji\v{c}, Jan
and Ivanova, Angelina and Ure\v{s}ov{\'a}, Zde\v{n}ka},
title = {Towards Comparability of Linguistic Graph Banks for Semantic Parsing},
booktitle = LREC:16
year = 2016,
address = L:LREC:16,
pages = {3991--3995}
Exactness criteria for SDP-relaxations of quadratic extremum problems
No full textИсследованы условия получения точных решений квадратичных экстремальных задач общего вида с помощью SDP-релаксаций. На основе известных результатов относительно точности двойственных оценок (лагранжевых релаксаций) и их взаимосвязи с SDP-релаксациями сформулирован ряд условий, при которых оптимальные значения целевых функций квадратичной экстремальной задачи и ее SDP-релаксации равны.Досліджено умови отримання точних розв’язків квадратичних екстремальних задач загального вигляду за допомогою SDP-релаксацій. На основі відомих результатів стосовно точності двоїстих оцінок (лагранжевих релаксацій) і їхнього взаємозв’язку з SDP-релаксаціями сформульовано ряд умов, при яких оптимальні значення цільових функцій квадратичної екстремальної задачі та її SDP-релаксації рівні.The author analyzes the conditions of obtaining exact solutions to quadratic extremum problems of general type by using SDP-relaxations. Based on the known results for exactness of dual bounds (lagrangian relaxations) and their relationship with SDP-relaxations, several conditions are formulated, under which the values of optimal objective function of the quadratic extremal problem and its SDP-relaxation are equal
Smaller SDP for SOS decomposition
No full textA popular numerical method to compute sum of squares (SOS of polynomials) decompositions for polynomials is to transform the problem into semi-definite programming (SDP) problems and then solve them by SDP solvers. In this paper, we focus on reducing the sizes of inputs to SDP solvers to improve the efficiency and reliability of those SDP based methods. Two types of polynomials, convex cover polynomials and split polynomials, are defined. A convex cover polynomial or a split polynomial can be decomposed into several smaller sub-polynomials such that the original polynomial is SOS if and only if the sub-polynomials are all SOS. Thus the original SOS problem can be decomposed equivalently into smaller sub-problems. It is proved that convex cover polynomials are split polynomials and it is quite possible that sparse polynomials with many variables are split polynomials, which can be efficiently detected in practice. Some necessary conditions for polynomials to be SOS are also given, which can help refute quickly those polynomials which have no SOS representations so that SDP solvers are not called in this case. All the new results lead to a new SDP based method to compute SOS decompositions, which improves this kind of methods by passing smaller inputs to SDP solvers in some cases. Experiments show that the number of monomials obtained by our program is often smaller than that by other SDP based software, especially for polynomials with many variables and high degrees. Numerical results on various tests are reported to show the performance of our program.National Science Foundation of China [11290141, 11271034]SCI(E)[email protected]; [email protected]
Shirley Williams, UK
No full textPeer, former MP and Cabinet Minister, co-Founder of Social Democratic Party (SDP
The campaign for democratic socialism 1960-1964.
No full textPhDIn early 1960 it seemed likely that the official Labour
Party defence policy would be defeated by a unilateralist
resolution at the Scarborough Conference. In response to
this possibility the Campaign for Democratic Socialism,
or CDS, was established.
The CDS projected the image of a grass-roots movement
inspired by Gaitskell's "fight and fight again" speech.
But it was run by a Campaign Committee which included
leading members of the Party like Tony Crosland, Roy
Jenkins and Patrick Gordon Walker, as well as less well
known members like Bill Rodgers, Dick Taverne, Philip
Williams, Brian Walden, Denis Howell and David Marquand.
This highly talented group launched an elaborate and
successful lobbying, publicity and briefing operation
which was influential in overturning the unilateralist
vote at the Blackpool Conference of 1961. After Blackpool
the Campaign helped many of its leading members find
seats in the House of Commons while continuing to put the
"revisionist" case through its newspaper Campaign.
The importance of the CDS in the history of the Labour
Party is, primarily, as the first internal pressure group
organised by the right of the Party. It was also the
first internal Party group to use such sophisticated
lobbying techniques. Moreover, the subsequent careers of
the leading members of the Campaign influenced the
development of the Labour Party. The CDS was an important
formative political action for many of them. Finally many
of the CDS supporters set-up or joined the SDP when it
was launched
An ideology in transition: the political though of the social democratic party
No full textThe thesis of this dissertation is that the political thought of the Social Democratic Party can be most adequately understood by an analysis of the relationship between liberty and equality within that political thought. By examining this relationship it may also be possible to indicate in which of the three major ideological traditions SDP political thought can be placed. The first chapter describes the history and ethos of social democracy focusing upon the disputes in the Labour Party between 1956 and 1981. The second, third and fourth chapters deal with the writings of Roy Jenkins, David Owen and Shirley Williams. Their writings are evaluated by the importance they place on liberty over equality or vice versa. The work looks at issues such as the ownership of wealth. The fifth chapter reviews the publications of the Tawney Society. The sane method is employed to assess these writings as used on the three SDP leaders. The conclusion suggests that the SDP has many traditions in its political thought. It has been influenced by events within the Labour Party. However, the dominant tradition would appear to be liberal and not socialist
Open SDP 1.2
No full textThe original SDP 2014 and 2015 data collections were made available under task-specific ‘evaluation’ licenses to registered SemEval participants. In mid-2016, all original data has been bundled with system submissions, supporting software, an additional SDP-style collection of semantic dependency graphs, and additional background material (from which some of the SDP target representations were derived) for release through the Linguistic Data Consortium (with LDC catalogue number LDC2016 T10).
One of the four English target representations (viz. DM) and the entire Czech data (in the PSD target representation) are not derivative of LDC-licensed annotations and, thus, can be made available for direct download (Open SDP; version 1.2; January 2017) under a more permissive licensing scheme, viz. the Creative Common Attribution-NonCommercial-ShareAlike license. This package also includes some ‘richer’ meaning representations from which the English bi-lexical DM graphs derive, viz. scope-underspecified logical forms and more abstract, non-lexicalized ‘semantic networks’. The latter of these are formally (if not linguistically) similar to Abstract Meaning Representation (AMR) and are available in a range of serializations, including in AMR-like syntax.
Version 1.1 was released April 2016. Version 1.2 adds the 2015 Turku system, which was accidentally left out from version 1.1.
Please use the following bibliographic reference for the SDP 2016 data:
@string{C:LREC = {{I}nternational {C}onference on
{L}anguage {R}esources and {E}valuation}}
@string{LREC:16 = {Proceedings of the 10th } # C:LREC}
@string{L:LREC:16 = {Portoro\v{z}, Slovenia}}
@inproceedings{Oep:Kuh:Miy:16,
author = {Oepen, Stephan and Kuhlmann, Marco and Miyao, Yusuke
and Zeman, Daniel and Cinkov{\'a}, Silvie
and Flickinger, Dan and Haji\v{c}, Jan
and Ivanova, Angelina and Ure\v{s}ov{\'a}, Zde\v{n}ka},
title = {Towards Comparability of Linguistic Graph Banks for Semantic Parsing},
booktitle = LREC:16
year = 2016,
address = L:LREC:16,
pages = {3991--3995}
Enhanced SDP-Dynamic Bloom Filters for a DDS Node Discovery in Real-time Distributed Systems
No full textInternational audience—In this paper, an enhanced SDP-Dynamic bloom filters for a DDS node discovery scheme in real-time distributed systems is proposed. Since the previous works of the DDS focuses more on the usage of a Simple Discovery Protocol (SDP) for endpoint to endpoint information communication of industrial-scale networks, attempts have now been made to enhance this approach into the Simple Discovery Protocol Dynamic Bloom Filters (SDP-Dynamic Bloom) focusing more on scalability in the amount of sent and stored message packets in the industrial network system. Simulation result show that the proposed scheme viciously reduce the overall computing and processing time of both stable and unstable industrial network environment which arises during the restructuring process of the existing SDP bloom filters approach
- …
