1,720,994 research outputs found
Online Revenue Maximization for Server Pricing
Get PDFEfficient and truthful mechanisms to price resources on remote
servers/machines has been the subject of much work in recent years due to the
importance of the cloud market. This paper considers revenue maximization in
the online stochastic setting with non-preemptive jobs and a unit capacity
server. One agent/job arrives at every time step, with parameters drawn from an
underlying unknown distribution.
We design a posted-price mechanism which can be efficiently computed, and is
revenue-optimal in expectation and in retrospect, up to additive error. The
prices are posted prior to learning the agent's type, and the computed pricing
scheme is deterministic, depending only on the length of the allotted time
interval and on the earliest time the server is available. If the distribution
of agent's type is only learned from observing the jobs that are executed, we
prove that a polynomial number of samples is sufficient to obtain a
near-optimal truthful pricing strategy
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe 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
Algorithms and complexity results for problems on fair division and imitation games
Get PDF"We study the problem of allocating indivisible goods to agents in a fair and efficient manner. We consider different notions of fairness such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) in conjuction with Pareto-optimality (PO). We present polynomial time algorithms for computing allocations that are EF1 and PO when (i) the number of agents is constant, and (ii) the number of different values that every agent has for the goods is constant. We also show that when there are exactly two values for the goods, an allocation that is EFX, PO and gives a 1.067-approximation to the Nash Social Welfare (NSW) can be computed in polynomial time. We also present algorithms that satisfy a different notions of fairness, like equitability up to one good (EQ1), and equitability up to any good (EQX) along with PO in some of these cases. On the complexity front, we show that the problem of computing EF1 and PO allocations belongs to class PLS. Further we show that deciding if EFX and PO allocations exist is NP-hard, even where there are at most two non-zero values for the goods.
We next consider the problem of computing the Nash Social Welfare maximizing allocation for the case of public goods subject to a cardinality constraint. We show that the NSW problem is NP-hard, even when the valuations are all binary. Next, we present a linear-factor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSW-preserving reductions from the model of private goods to that of public goods, and from the public goods model to that of public decision making, thus showing how the models are related.
Lastly, we study the problem of computing approximate Nash equilibria in imitation games. An imitation game is represented by two payoff matrices , in which is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates"" the first. We show that much like the general case, for any , computing a -approximate NE of imitation games remains PPAD-hard, where is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find -approximate NE for any given constant (PTAS). The former result also rules out the smooth complexity being in \Ptime, unless \PPAD \subset \RP."Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2022-08-01The student, Aniket Murhekar, accepted the attached license on 2020-07-17 at 20:25.The student, Aniket Murhekar, submitted this Thesis for approval on 2020-07-17 at 20:34.This Thesis was approved for publication on 2020-07-20 at 10:18.DSpace SAF Submission Ingestion Package generated from Vireo submission #15689 on 2020-10-02 at 15:51:47Made available in DSpace on 2020-10-07T22:50:05Z (GMT). No. of bitstreams: 2
MURHEKAR-THESIS-2020.pdf: 479836 bytes, checksum: 9b218fda07cba3a8d088ffdfa2255d91 (MD5)
LICENSE.txt: 4212 bytes, checksum: 27635a26a37e7e16ffcd5eed856a1b62 (MD5)
Previous issue date: 2020-07-20Embargo set by: Seth Robbins for item 116350
Lift date: 2022-10-07T22:50:13Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemAuthor requested closed access (OA after 2yrs) in Vireo ETD systemLimite
Variations on the Author
Get PDF“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
Get PDFWe 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
The complexity of continuous local search
Get PDFThe complexity class CLS was introduced by Daskalakis and Papadimitriou in [9] with the goal of capturing the complexity of some well-known problems in PPAD ∩ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. No complete problem was known for CLS, and in [9], the problems CONTRACTION, i.e., the problem of finding an approximate fixpoint of a contraction map, and P-LCP, i.e., the problem of solving a P-matrix Linear Complementarity Problem, were identified as prime candidates.
First, we present the first complete problem for CLS, METAMETRICCONTRACTION, which is closely related to the problem CONTRACTION.
Second, we introduce ENDOFPOTENTIALLINE, which captures aspects of PPAD and PLS directly via a monotonic directed path, and show that ENDOFPOTENTIALLINE is in CLS via a two-way reduction to ENDOFMETEREDLINE. The latter was defined in [18] to keep track of how far a vertex is on the PPAD path via a restricted potential function, and was shown to be in CLS.
Third, we reduce P-LCP to ENDOFPOTENTIALLINE, thus making ENDOFPOTENTIALLINE and ENDOFMETEREDLINE at least as likely to be hard for CLS as P-LCP. This result leverages the monotonic structure of Lemke paths for P-LCP problems, making ENDOFPOTENTIALLINE a likely candidate to capture the exact complexity of P-LCP; we note that the structure of Lemke-Howson paths for finding a Nash equilibrium in a two-player game directly motivated the definition of the complexity class PPAD, which ended up capturing this problem’s complexity exactly.
Finally, we reduce the 2-dimensional version of CONTRACTION to ENDOFPOTENTIALLINE, providing further evidence that ENDOFPOTENTIALLINE is CLS-hard.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo termsThe student, Spencer Gordon, accepted the attached license on 2017-04-18 at 10:36.The student, Spencer Gordon, submitted this Thesis for approval on 2017-04-18 at 10:42.This Thesis was approved for publication on 2017-04-21 at 13:26.DSpace SAF Submission Ingestion Package generated from Vireo submission #10848 on 2017-08-10 at 13:42:04Made available in DSpace on 2017-08-10T19:15:22Z (GMT). No. of bitstreams: 2
GORDON-THESIS-2017.pdf: 1649950 bytes, checksum: b2aaf6c871d2798b66a35a16014b34ae (MD5)
LICENSE.txt: 4211 bytes, checksum: c89ffff8b0ea5714f835bace2a495f86 (MD5)
Previous issue date: 2017-04-2
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe 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
- …
