Noticias en español
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time.
Abstract: Abstract: In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta, Talwar and Witmer [STOC 2013] obtained a 2-approximation with polynomial running time for fixed k, and the question of whether there exists a c-approximation...
Read MoreOrienting (hyper)graphs under explorable stochastic uncertainty.
Abstract: Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where...
Read MoreGeneralized Malleable Scheduling via Discrete Concavity.
Abstract: In malleable scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptively and in unison, i.e., it has to occupy the same time interval on all its allocated machines. In this talk, we discuss a generalization of malleable scheduling, in which a function f(S, j) determines the processing time of job j on machine subset S. Under different discrete concavity assumptions on 1/f(S,j), we show that the scheduling problem can be approximated by a considerably...
Read MoreOn the general problem of Erdos and Nesetril and its offsprings.
Abstract: In 1988, Erdos wrote about a problem he proposed with Nesetril: “One could perhaps try to determine the smallest integer h_t(D) for which every graph, with size h_t(D) edges and maximum degree at most D, contains two edges so that the shortest path joining these edges has length at least t. This problem seems to be interesting only if there is a nice expression for h_t(D).” This problem can be considered as the edge version of the famous (and hard) degree-diameter problem. It was the inspiration for a series of research papers on variants of this problem, where one is...
Read MoreAuctions with Intermediaries.
Abstract: In many markets, buyers do not bid directly in the auction, but instead, they are represented by intermediaries. This includes ad auctions, where some of the buyers might be represented by intermediaries like Ad agencies, Aggregators (e.g. Home Advisor), or Ad networks participating in an Ad Exchange. The presence of intermediaries creates the potential for collusion across buyers. Also, intermediaries have their own goals that depend on the contract between buyers and the intermediary, and will behave according to the incentives induced by their goals. We will talk about the...
Read MoreSome discrete optimization problems in matching markets.
Abstract: In the classical stable marriage problem, we are given two sets of agents – students and schools – with each student and school having a total order of agents from the opposite set. The goal is to form disjoint pairs of students and schools so that the resulting matching satisfies a fairness property known as stability. In their fundamental work, Gale and Shapley showed that a stable matching always exists and gave a fast algorithm to find one. These strong structural and algorithmic results propelled the application of the stable marriage model in several contexts,...
Read More