2,028 research outputs found
Small minors in dense graphs
No full textA fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions f and h such that every graph with n vertices and average degree at least f(t) contains a K t-model with at most h(t){dot operator}logn vertices. The logarithmic dependence on n is best possible (for fixed t). In general, we prove that f(t)≤2 t-1+ε For t≤4, we determine the least value of f(t); in particular, f(3)=2+ε and f(4)=4+ε For t≤4, we establish similar results for graphs embedded on surfaces, where the size of the K t-model is bounded (for fixed t). © 2012 Samuel Fiorini, Gwenaël Joret, Dirk Oliver Theis, David R. Wood.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
The VPN problem with concave costs
No full textOnly recently Goyal, Olver, and Shepherd [Pr oc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms, 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry. © 2010 Societ y for Industrial and Applied Mathematics.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Entertainer: Pieter-Dirk Uys
No full textThis booklet celebrates the life and work of Pieter-Dirk Uys, internationally acclaimed playwright, author, role-model and one of South Africa's living treasures
Entertainer: Pieter-Dirk Uys
No full textThis booklet celebrates the life and work of Pieter-Dirk Uys, internationally acclaimed playwright, author, role-model and one of South Africa's living treasures
Entertainer: Pieter-Dirk Uys
No full textThis booklet celebrates the life and work of Pieter-Dirk Uys, internationally acclaimed playwright, author, role-model and one of South Africa's living treasures
Formal Techniques and Self/Other Relations in the Novels of Dirk Bogarde
No full textThe thesis foregrounds the distinctive contribution Dirk Bogarde made to
contemporary writing in a second career that developed in parallel to his screen
commitments. It dispels the notion that Bogarde followed a familiar path as an actor
who wrote books. Instead it establishes his reputation as an innovative writer whose
formal technique was substantially influenced by the textual systems of cinema and
the cross-fertilisation from acting to writing.
In examining the formative factors that steered Bogarde towards authorship, the
thesis addresses the role of performance as a generative factor in the evolution of the
novels, establishing a discursive link with Bakhtinian dialogism, and specifically,
transgredience as a formal imperative. Secondly, it affords a critical insight into why
the major concerns with staging and performativity preoccupy his writing career.
The thesis claims that Bogarde was an empirically dialogical writer whose use
of camera-eye narration fostered the proliferation of competing discourses across the
fiction. This formal dynamic is centred on the relationship between stages and
dialogism, which incorporates the work of Erving Goffinan as a complementary
critique to Bakhtinian theory with its emphasis on self-presentation. The concern
with socially-constructed behaviour leads the thesis to address the associated issues of
stereotyping and 'otherness', which in terms of body politics is articulated by the
mono logic drive to confine the sexual 'other' to a fixed representation.
Bogarde's ability to draw on cinematic and performance techniques identifies
an area of expertise unavailable to most other writers. This is an unusual repository
of skills to bring to writing which is why the thesis makes the claim for his singular
achievement as a contemporary author. There are fruitful points of intersection to be
explored in this respect with the work of Christopher Isherwood, whom Bogarde read
and admired, as a basis for further research. It is hoped that the thesis will play its
part in opening up new possibilities for Bogarde's writing to be re-visited by future
critics
"The end of national models? Integration courses and citizenship trajectories in Europe"
No full textSeveral European countries have recently introduced or are planning to introduce citizenship trajectories (voluntary or obligatory inclusion programs for recent immigrants) or citizen integration tests (tests one should pass to be able and acquire permanent residence or state citizenship). Authors like Joppke claim this is an articulation of a more general shift towards the logic of assimilation (and away from a multicultural agenda) in integration policy paradigms of European States. Integration policies would even be converging in such a fashion that it would no longer make sense to think in terms of national models for immigrant integration. One cannot deny the empirical fact of diffusion of civic integration policies throughout Europe. This paper claims there is, however, still sufficient distinctiveness between immigrant integration policies in order to continue and use an analytical framework which distinguishes national models
Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar 15082 "Limitations of convex programming: lower bounds on extended formulations and factorization ranks" held in February 2015. Summaries of a selection of talks are given in addition to a list of open problems raised during the seminar
BROJA-2PID: A Robust Estimator for Bivariate Partial Information Decomposition
No full textMakkeh, Theis, and Vicente found that Cone Programming model is the most robust to compute the Bertschinger et al. partial information decomposition (BROJA PID) measure. We developed a production-quality robust software that computes the BROJA PID measure based on the Cone Programming model. In this paper, we prove the important property of strong duality for the Cone Program and prove an equivalence between the Cone Program and the original Convex problem. Then, we describe in detail our software, explain how to use it, and perform some experiments comparing it to other estimators. Finally, we show that the software can be extended to compute some quantities of a trivaraite PID measure
- …
