1,720,980 research outputs found
Parameterized algorithms for block-structured integer programs with large entries
Full text linkWe study two classic variants of block-structured integer programming.
Two-stage stochastic programs are integer programs with constraints of the form
A_i x + D_i y_i = b_i for all i = 1, ..., n,
where A_i and D_i are bounded-size matrices. Intuitively, after choosing a small set of global variables x, the problem decomposes into many bounded-size subproblems.
n-fold programs are integer programs with constraints of the form
(∑_i C_i y_i = a) and (D_i y_i = b_i for all i = 1, ..., n),
again with bounded-size matrices C_i and D_i. This captures knapsack-like settings where variables are partitioned into small groups that obey local constraints, while a few global constraints link all variables.
Recent work shows that optimization for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable (FPT) when parameterized by the dimensions of the relevant matrices A_i, C_i, D_i and by the maximum absolute entry in the constraint matrix. A key tool is the Graver basis, which assumes all constraint entries are bounded.
We prove that these FPT results persist even when large entries are allowed in the global part of the program:
Two-stage stochastic programs (feasibility): FPT when parameterized by the dimensions of A_i and D_i and by the maximum absolute entry of D_i. In particular, A_i may have arbitrarily large entries.
Uniform n-fold integer programs (linear optimization): FPT when parameterized by the dimensions of C_i and D_i and by the maximum absolute entry of D_i, provided all C_i are equal to a common matrix C; C may have arbitrarily large entries.
The uniformity requirement in the second result is necessary: without it, the problem is NP-hard even for constant parameter values. Both algorithms are weakly polynomial, with running time measured in the total bit size of the input.
Methodologically, we move beyond a purely Graver-basis approach. For two-stage stochastic programs, we reduce to an integer program with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce the given instance to an exponential-size program with bounded right-hand sides, and then solve it via a reduction to mixed-integer programming with a bounded number of integral variables
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Full text linkWe solve the Bin Packing problem in time, where is the number
of items less or equal to one third of the bin capacity. This parameter
measures the distance from the polynomially solvable case of only large (i.e.,
greater than one third) items. Our algorithm is actually designed to work for a
more general Vector Bin Packing problem, in which items are multidimensional
vectors. We improve over the previous fastest time
algorithm.
Our algorithm works by reducing the problem to finding an exact weight
perfect matching in a (multi-)graph with edges, whose weights are
integers of the order of . To solve the matching problem in the
desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani
algorithm with only a linear dependence on the edge weights and the number of
edges, which may be of independent interest.
Moreover, we give a tight lower bound, under the Strong Exponential Time
Hypothesis (SETH), showing that the constant in the base of the exponent
cannot be further improved for Vector Bin Packing.
Our techniques also lead to improved algorithms for Vector Multiple Knapsack,
Vector Bin Covering, and Perfect Matching with Hitting Constraints.Comment: ICALP 202
Parameterized algorithms for block-structured integer programs with large entries
Full text linkWe study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1, ..., n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form (Equation presented) Ciyi = a and Diyi = bi for all i = 1, ..., n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables. A line of recent work established that the optimization problem for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable when parameterized by the dimensions of relevant matrices Ai, Ci, Di and by the maximum absolute value of any entry appearing in the constraint matrix. A fundamental tool used in these advances is the notion of the Graver basis of a matrix, and this tool heavily relies on the assumption that all the entries of the constraint matrix are bounded. In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: • The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices Ai, Di and by the maximum absolute value of the entries of matrices Di. That is, we allow matrices Ai to have arbitrarily large entries. • The linear optimization problem for n-fold integer programs that are uniform - all matrices Ci are equal - is fixed-parameter tractable when parameterized by the dimensions of matrices Ci and Di and by the maximum absolute value of the entries of matrices Di. That is, we require that Ci = C for all i = 1, ..., n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. In both results, we depart from the approach that relies purely on Graver bases. Instead, for two-stage stochastic programs, we devise a reduction to integer programming with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce a given n-fold program to an exponential-size program with bounded right-hand sides, which we consequently solve using a reduction to mixed integer programming with a bounded number of integral variables.</p
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
koamabayili/VECTRON-author-checklist: VECTRON author checklist
No full textWe have done our best to complete the author checklist relating to the use of animals in the hut study. Note that the objective for the hut study was to evaluate the IRS treatment applications for residual efficacy against Anopheles mosquitoes, including the local An. coluzzii mosquito population. Cows were only used to attract mosquitoes into the huts and no tests were carried out directly on the cows. The author checklist is intended for use with studies where experiments are carried out on animals, which is why we have had such difficulty in completing this for the hut study, as many of the questions do not relate to how the cows were used
- …
