Search Results

In the paper “Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation,” the authors develop a novel algorithm analysis approach to address stochastic elements in online matching. The approach leads to several new ...

The problem of online matching with stochastic rewards is a generalization of the online bipartite matching problem where each edge has a probability of success. When a match is made it succeeds with the probability of the corresponding edge. We consider ...

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with ...

We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration d after which ...

Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean k-median and k-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent ...

Obtaining strong linear relaxations for capacitated covering problems constitutes a significant technical challenge. For one of the most basic cases, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. We generalize the ...

When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be incurred from the expensive task of saving the memory’s state or from loading data into and out of memory. ...

This paper presents a primal-dual weak Galerkin finite element method for a class of second order elliptic equations of Fokker--Planck type. The method is based on a variational form where all the derivatives are applied to the test functions so that no ...

We study inertial versions of primal-dual proximal splitting, also known as the Chambolle--Pock method. Our starting point is the preconditioned proximal point formulation of this method. By adding correctors corresponding to the antisymmetric part of the ...

Given a weighted planar bipartite graph G(A ∪ B, E) where each edge has an integer edge cost, we give an Õ(n^4/3log nC) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best-known ...

Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for $k$-means in Euclidean space with a provable guarantee is a simple ...

The primal-dual hybrid gradient method, modified (PDHGM, also known as the Chambolle--Pock method), has proved very successful for convex optimization problems involving linear operators arising in image processing and inverse problems. In this paper, we ...

In sensitive applications, machines need to be periodically calibrated to ensure that they run to high standards. Creating an efficient schedule on these machines requires attention to two metrics: ensuring good throughput of the jobs, and ensuring that ...

We study the extension of the Chambolle--Pock primal-dual algorithm to nonsmooth optimization problems involving nonlinear operators between function spaces. Local convergence is shown under technical conditions including metric regularity of the ...

The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contributed, among other things, new models (notably stochastic) and extensions ...

Cardiac diffusion tensor MR imaging DT-MRI allows to analyze 3D fiber organization of the myocardium which may enhance the understanding of, for example, cardiac remodeling in conditions such as ventricular hypertrophy. Diffusion-weighted MRI DW-MRI ...

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors and provide a tight analysis of the algorithm’s competitiveness. Our results generalize and improve upon work by Chan et al. [2010], which considers a ...

Many real-world phenomena exhibit strong hierarchical structure. Consequently, in many real-world directed social networks vertices do not play equal role. Instead, vertices form a hierarchy such that the edges appear mainly from upper levels to ...

A natural optimization model that formulates many online resource allocation problems is the online linear programming LP problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a ...

A natural optimization model that formulates many online resource allocation problems is the online linear programming LP problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a ...

<P>A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In ...