646 research outputs found
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
No full textIn the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt} where M_{Opt} is the minimum cost matching between S and R.
We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log^2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
No full textWe study the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given point sets S and R which correspond to the server and request locations; here |S|=|R|=n. All these locations are points from some metric space and the cost of matching a server to a request is given by the distance between their locations in this space. In this problem, the request points arrive one at a time. When a request arrives, we must immediately and irrevocably match it to a "free" server. The matching obtained after all the requests are processed is the online matching M. The cost of M is the sum of the cost of its edges. The performance of any online algorithm is the worst-case ratio of the cost of its online solution M to the minimum-cost matching.
We present a deterministic online algorithm for this problem. Our algorithm is the first to simultaneously achieve optimal performances in the well-known adversarial and the random arrival models. For the adversarial model, we obtain a competitive ratio of 2n-1 + o(1); it is known that no deterministic algorithm can do better than 2n-1. In the random arrival model, our algorithm obtains a competitive ratio of 2H_n - 1 + o(1); where H_n is the n-th Harmonic number. We also prove that any online algorithm will have a competitive ratio of at least 2H_n - 1-o(1) in this model.
We use a new variation of the offline primal-dual method for computing minimum cost matching to compute the online matching. Our primal-dual method is based on a relaxed linear-program. Under metric costs, this specific relaxation helps us relate the cost of the online matching with the offline matching leading to its robust properties
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
No full textWe present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time.
When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilon-approximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d-1)/(2d-1)}) poly log n time algorithm for computing epsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HK-Algorithm
Supplemental material - Influence of crural vessel run-off on short- and mid-term outcomes following femoro-popliteal bypass grafting
No full textSupplemental material for Influence of crural vessel run-off on short- and mid-term outcomes following femoro-popliteal bypass grafting by Ryan Preece, Lydia Mann, Sachin R Kulkarni and Sharath CV Paravastu in Vascular</p
10.1177_1358863X19865610_Supplemental_tables – Supplemental material for Delayed gratification and adherence to exercise among patients with claudication
No full textSupplemental material, 10.1177_1358863X19865610_Supplemental_tables for Delayed gratification and adherence to exercise among patients with claudication by Sherene E Sharath, MinJae Lee, Panos Kougias, Wendell C Taylor, Nader Zamani and Neal R Barshes in Vascular Medicine</p
Terahertz disk resonator on a substrateless dielectric waveguide platform
No full textPublished 31 August 2023Abstract not availablePanisa Dechwechprasit, Rajour Tanyi Ako, Sharath Sriram, Christophe Fumeaux, and Withawat Withayachumnanku
Improved Approximate Rips Filtrations with Shifted Integer Lattices
No full textRips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For n points in R^d, we present a scheme to construct a 4.24-approximation of the multi-scale filtration of the Rips complex in the L-infinity metric, which extends to a O(d^{0.25})-approximation of the Rips filtration for the Euclidean case. The k-skeleton of the resulting approximation has a total size of n2^{O(d log k)}. The scheme is based on the integer lattice and on the barycentric subdivision of the d-cube
Dataset: A Cross-Platform and Cross-Interaction Study of User Personality based on Images on Twitter and Flickr
No full textThis folder contains the following dataset: Crossed-Linked Flickr and Twitter dataset.Psycho-Flickr consists of a set of users who answered the BFI survey. We collected profile and up to 300 posted and liked pictures for each user. Please contact Christina Segalin (http://www.cristinasegalin.com/) for access to these labels.Crossed-Linked Flickr and Twitter consists of a set of users with active accounts both on Flickr and Twitter.We used text mining approaches to predict personality traits for this set of users.We collected profile and up to 300 posted and liked picture for each user. Twitter or Flickr user ids with their text-predicted/BFI survey Big-Five personality scores are presented.Features extracted from profile images and averaged over posted and Liked Images are presented that include :Colors FeaturesCNN Generic Features: 4096 dim penultimate layer features of VGG_NetCNN object and scene categories:VGG_Net prediction on 1000 objects and 365 scene categoriesImagga tagsBig five personality traits are in this order:(ope: openness, con: conscientiousness, ext: extraversion, agr: agreeableness, and neu: neuroticism)For more information/questions about the dataset, please contact Sharath Chandra (chandrasg.github.io)If using this data set, please cite the following publication:@inproceedings{guntuku2017studying, title={Cross-platform and cross-interaction study of user personalitybased on images on Twitter and Flickr }, author={Zahra Riahi Samani, Sharath Chandra Guntuku, Mohsen Ebrahimi Moghaddam, DanielPreotiuc-Pietro, Lyle H. Ungar}, booktitle={Plos One Submission}, pages={}, year={2018}, organization={}}</div
Feasibility and safety of Reveal LINQ insertion in a sterile procedure room versus electrophysiology laboratory
No full textAbstract not availableGeoffrey R. Wong, Dennis H. Lau, Melissa E. Middeldorp, Judith A. Harrington, Simon Stolcman, Lauren Wilson, Darragh J. Twomey, Sharath Kumar, Dian A. Munawar, Kashif B. Khokhar, Rajiv Mahajan, Prashanthan Sander
Polynomial-Sized Topological Approximations Using the Permutahedron
No full textClassical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in R^d, we obtain a O(d)-approximation with at most n2^{O(d log k)} simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))-approximation of size n^{O(1)} for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry.
Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+epsilon)-approximation of the Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1)
- …
