Uriel Feige, Ariel Sapir, Laliv Tauber,
We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang [JACM, 2018] present instances for which every allocation gives some agent less than her maximin share. We present such examples with larger gaps. For three agents and nine items, we design an instance in which at least one agent does not get more than a $$\frac{39}{40}$$ fraction of her maximin share. Moreover, we show that there is no negative example in which the difference ...
Tópico(s): Complexity and Algorithms in Graphs
2022 - Springer Science+Business Media | Lecture notes in computer science
Moshe Babaioff, Tomer Ezra, Uriel Feige,
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation ...
Tópico(s): Auction Theory and Applications
2021 - Association for the Advancement of Artificial Intelligence | Proceedings of the AAAI Conference on Artificial Intelligence
Ofir Raz, Tamir Biezuner, Adam Spiro, Shiran Amir, Lilach Milo, Alon Titelman, Amos Onn, Noa Chapal-Ilani, Liming Tao, Tzipy Marx, Uriel Feige, Ehud Shapiro,
Short tandem repeats (STRs) are polymorphic genomic loci valuable for various applications such as research, diagnostics and forensics. However, their polymorphic nature also introduces noise during in vitro amplification, making them difficult to analyze. Although it is possible to overcome stutter noise by using amplification-free library preparation, such protocols are presently incompatible with single cell analysis and with targeted-enrichment protocols. To address this challenge, we have designed ...
Tópico(s): RNA Research and Splicing
2019 - Oxford University Press | Nucleic Acids Research
Uriel Feige, Michael Krivelevich, Daniel Reichman,
We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors. A contagious set is a set whose activation results with the entire graph being active. Given a graph $G$, let $m(G,r)$ be the minimal size of a contagious set. We study this process on the binomial random graph $G:=G(n,p)$ with $p:=\frac{d}{n}$ and $1\ll d\ll (\frac{n\log\log n}{\log^{2}n})^{\frac{r-1}{ ...
Tópico(s): Stochastic processes and statistical mechanics
2017 - Institute of Mathematical Statistics | The Annals of Applied Probability
Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis,
We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MPH-m (where m is the total number of items) captures all monotone functions. The lowest level, MPH-1, captures all monotone submodular functions, and more generally, the class of functions known as XOS. Every monotone function that has a positive hypergraph ...
Tópico(s): Economic theories and models
2015 - Association for the Advancement of Artificial Intelligence | Proceedings of the AAAI Conference on Artificial Intelligence
Jonathan Blakes, Ofir Raz, Uriel Feige, Jaume Bacardit, Paweł Widera, Tuval Ben-Yehezkel, Ehud Shapiro, Natalio Krasnogor,
De novo DNA synthesis is in need of new ideas for increasing production rate and reducing cost. DNA reuse in combinatorial library construction is one such idea. Here, we describe an algorithm for planning multistage assembly of DNA libraries with shared intermediates that greedily attempts to maximize DNA reuse, and show both theoretically and empirically that it runs in linear time. We compare solution quality and algorithmic performance to the best results reported for computing DNA assembly ...
Tópico(s): DNA and Nucleic Acid Chemistry
2014 - American Chemical Society | ACS Synthetic Biology
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Seffi, Roy Schwartz,
We study graph partitioning problems from a min-max perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equal size, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$ approximation algorithm. This ...
Tópico(s): VLSI and FPGA Design Techniques
2014 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Arash Asadpour, Uriel Feige, Amin Saberi,
We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem . There are m items and n players. Every item has some nonnegative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovász local ...
Tópico(s): Optimization and Search Problems
2012 - Association for Computing Machinery | ACM Transactions on Algorithms
Uriel Feige, Vahab Mirrokni, J. Vondrák,
Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper, we design the first constant-factor approximation algorithms for maximizing nonnegative (non-monotone) submodular functions. In particular, we give a deterministic ...
Tópico(s): Computational Geometry and Mesh Generation
2011 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Chandan K. Dubey, Uriel Feige, Walter Unger,
The bandwidth of an n-vertex graph G is the minimum value b such that the vertices of G can be mapped to distinct integer points on a line without any edge being stretched to a distance more than b. Previous to the work reported here, it was known that it is NP-hard to approximate the bandwidth within a factor better than 3/2. We improve over this result in several respects. For certain classes of graphs (such as cycles of cliques) for which it is easy to approximate the bandwidth within a factor ...
Tópico(s): Computational Geometry and Mesh Generation
2010 - Elsevier BV | Journal of Computer and System Sciences
In the hidden clique problem, one needs to find the maximum clique in an $n$-vertex graph that has a clique of size $k$ but is otherwise random. An algorithm of Alon, Krivelevich and Sudakov that is based on spectral techniques is known to solve this problem (with high probability over the random choice of input graph) when $k \geq c \sqrt{n}$ for a sufficiently large constant $c$. In this manuscript we present a new algorithm for finding hidden cliques. It too provably works when $k > c \sqrt{n}$ for a sufficiently ...
Tópico(s): Limits and Structures in Graph Theory
2010 - French association | Discrete Mathematics & Theoretical Computer Science
We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least $1/2$ that of the value of the fractional solution. This approximation ratio of $1/2$ is an improvement over an $\Omega(1/\log m)$ ratio of Dobzinski, Nisan, and Schapira [Proceedings of the 37th Annual ACM Symposium on ...
Tópico(s): Game Theory and Voting Systems
2009 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee,
We develop the algorithmic theory of vertex separators and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into $L_1$ (and even Euclidean embeddings) are insufficient but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an $O(\sqrt{\log n})$ approximation for minimum ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the ...
Tópico(s): Optimization and Search Problems
2008 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Arash Asadpour, Uriel Feige, Amin Saberi,
We consider the problem of max-min fair allocation of indivisible goods. Our focus will be on the restricted version of the problem in which there are m items, each of which associated with a non-negative value. There are also n players and each player is only interested in some of the items. The goal is to distribute the items between the players such that the least happy person is as happy as possible, i.e. one wants to maximize the minimum of the sum of the values of the items given to any player. ...
Tópico(s): Optimization and Search Problems
2008 - Springer Science+Business Media | Lecture notes in computer science
Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour,
We prove semilogarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, assuming that $\mathrm{NP}\not\subseteq\operatorname{BPTIME}(2^{n^\varepsilon})$ for an arbitrary $\varepsilon>0$, we prove $O(1/\log^{\sigma}n)$ inapproximability for some constant $\sigma=\sigma(\varepsilon)$. We also prove $O(1/\log^{1/3-\varepsilon}n)$ inapproximability for any $\varepsilon> ...
Tópico(s): Cryptography and Data Security
2008 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge weights satisfy the triangle inequality, and one is required to find a minimum weight walk that visits all vertices. In the asymmetric traveling salesperson problem (ATSP) the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP), the walk is required to start at vertex s and to end at vertex t. We improve the approximation ratio for ATSP from $\frac{4}{3}\log_3 ...
Tópico(s): Complexity and Algorithms in Graphs
2007 - Springer Science+Business Media | Lecture notes in computer science
Tópico(s): Computational Geometry and Mesh Generation
2007 - Springer Science+Business Media | Algorithmica
Uriel Feige, Vahab Mirrokni, J. Vondrák,
Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.
Tópico(s): RFID technology advancements
2007 - Institute of Electrical and Electronics Engineers | Annual Symposium on Foundations of Computer Science
Uriel Feige, Guy Kindler, Ryan O’Donnell,
Motivated by the study of parallel repetition and also by the unique games conjecture, we investigate the value of the "odd cycle games" under parallel repetition. Using tools from discrete harmonic analysis, we show that after d rounds on the cycle of length m, the value of the game is at most 1-(1/m)ldrOmega macr(radicd) (for dlesm 2 , say). This beats the natural barrier of 1-Theta(1/m) 2 ldrd for Raz-style proofs and also the SDP bound of Feige-Lovasz; however, it just barely fails to have implications ...
Tópico(s): Advanced Graph Theory Research
2007 - Institute of Electrical and Electronics Engineers | Proceedings - IEEE Conference on Computational Complexity/Proceedings
We prove the following inequality: for every positive integer n and every collection $X_1, \ldots, X_n$ of nonnegative independent random variables, each with expectation 1, the probability that their sum remains below $n+1$ is at least $\alpha > 0$. Our proof produces a value of $\alpha = 1/13 \simeq 0.077$, but we conjecture that the inequality also holds with $\alpha = 1/e \simeq 0.368$. As an example for the use of the new inequality, we consider the problem of estimating the average degree of a graph by querying ...
Tópico(s): Optimization and Search Problems
2006 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Uriel Feige, Elchanan Mossel, Dan Vilenchik,
Experimental results show that certain message passing algorithms, namely, survey propagation, are very effective in finding satisfying assignments in random satisfiable 3CNF formulas. In this paper we make a modest step towards providing rigorous analysis that proves the effectiveness of message passing algorithms for random 3SAT. We analyze the performance of Warning Propagation, a popular message passing algorithm that is simpler than survey propagation. We show that for 3CNF formulas generated ...
Tópico(s): Cooperative Communication and Network Coding
2006 - Springer Science+Business Media | Lecture notes in computer science
Robert Krauthgamer, Uriel Feige,
A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size $n/2$. The bisection cost is the number of edges connecting the two sets. The problem of finding a bisection of minimum cost is prototypical to graph partitioning problems, which arise in numerous contexts. This problem is NP-hard. We present an algorithm that finds a bisection whose cost is within a factor of $O(\log^{1.5} n)$ from the minimum. For graphs excluding any fixed graph as a minor (e.g., planar ...
Tópico(s): Advanced Graph Theory Research
2006 - Society for Industrial and Applied Mathematics | SIAM Review
We observe that combining the techniques of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an O(lognloglogn)-approximation for the minimum-linear arrangement problem. This improves over the O(logn)-approximation of Rao and Richa.
Tópico(s): Algorithms and Data Compression
2006 - Elsevier BV | Information Processing Letters
Uriel Feige, Abraham D. Flaxman, Jason D. Hartline, Robert Kleinberg,
We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of 7600 on its competitive ratio); our analysis improves the bound to 15. In support of the conjecture that random sampling auction is in fact 4-competitive, we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.
Tópico(s): Mobile Crowdsensing and Crowdsourcing
2005 - Springer Science+Business Media | Lecture notes in computer science
Dan Frumkin, Adam Wasserstrom, Shai Kaplan, Uriel Feige, Ehud Shapiro,
What is the lineage relation among the cells of an organism? The answer is sought by developmental biology, immunology, stem cell research, brain research, and cancer research, yet complete cell lineage trees have been reconstructed only for simple organisms such as Caenorhabditis elegans. We discovered that somatic mutations accumulated during normal development of a higher organism implicitly encode its entire cell lineage tree with very high precision. Our mathematical analysis of known mutation ...
Tópico(s): Gene Regulatory Network Analysis
2005 - Public Library of Science | PLoS Computational Biology
A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/loglog n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor ...
Tópico(s): Computational Geometry and Mesh Generation
2005 - Springer Science+Business Media | Lecture notes in computer science
Abstract We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ 1 ≥ … ≥ λ n be the eigenvalues of an n ‐vertex graph, and let λ = max[λ 2 ,|λ n |]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ 1 ≥ d , and we show that $\lambda = O(\sqrt{d})$ . For d = c it is no longer true that $\lambda = O(\sqrt{d})$ , but we show that by removing a small number of vertices of highest degree in G , one gets a graph G ′ for which $\lambda = O(\sqrt{d})$ . Our proofs are ...
Tópico(s): Limits and Structures in Graph Theory
2005 - Wiley | Random Structures and Algorithms
We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ1 ≥ … ≥ λn be the eigenvalues of an n-vertex graph, and let λ = max[λ2,|λn|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ1 ≥ d, and we show that $\lambda = O(\sqrt{d})$. For d = c it is no longer true that $\lambda = O(\sqrt{d})$, but we show that by removing a small number of vertices of highest degree in G, one gets a graph G′ for which $\lambda = O(\sqrt{d})$. Our proofs are based ...
Tópico(s): Advanced Graph Theory Research
2005 - Wiley | Random Structures and Algorithms
Uriel Feige, Daniele Micciancio,
Tópico(s): Cryptography and Data Security
2004 - Elsevier BV | Journal of Computer and System Sciences
Uriel Feige, Michael Langberg,
Several combinatorial optimization problems can be approximated using algorithms based on semidefinite programming. In many of these algorithms a semidefinite relaxation of the underlying problem is solved yielding an optimal vector configuration v1,...,vn. This vector configuration is then rounded into a {0, 1} solution. We present a procedure called RPR2 (Random Projection followed by Randomized Rounding) for rounding the solution of such semidefinite programs. We show that the random hyperplane ...
Tópico(s): VLSI and FPGA Design Techniques
2004 - Academic Press | Journal of Algorithms