Related Research Articles
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.
Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.
Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.
Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.
In the mathematical field of graph theory, an instance of the Steiner tree problem is said to be quasi-bipartite if the non-terminal vertices in G form an independent set, i.e. if every edge is incident on at least one terminal. This generalizes the concept of a bipartite graph: if G is bipartite, and R is the set of vertices on one side of the bipartition, the set R is automatically independent.
In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector spaces or free modules are generally considered.
In mathematics, the minimum k-cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.
In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = (V, E) be an undirected graph and let S = (VS, ES) be a subgraph of G. Then the density of S is defined to be:
The balls into binsproblem is a classic problem in probability theory that has many applications in computer science. The problem involves m balls and n boxes. Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look at the number of balls in each bin; we call this number the load on the bin. The problem can be modelled using a Multinomial distribution, and may involve asking a question such as: What is the expected number of bins with a ball in them?
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.
The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:
When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.
In mechanism design, a branch of economics, a budget-feasible mechanism is a mechanism in which the total payment made by the auctioneer is upper-bounded by a fixed pre-specified budget. They were first presented by Yaron Singer, and studied by several others.
Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.
In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.
In computational economics, a single-minded agent is an agent who wants only a very specific combination of items. The valuation function of such an agent assigns a positive value only to a specific set of items, and to all sets that contain it. It assigns a zero value to all other sets. A single-minded agent regards the set of items he wants as purely complementary goods.
The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.
References
- ↑ Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (January 2018), "Approximating the Nash Social Welfare with Budget-Additive Valuations", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 2326–2340, doi: 10.1137/1.9781611975031.150 , hdl: 11858/00-001M-0000-002D-E7D6-2 , ISBN 978-1-61197-503-1, S2CID 1282865
- ↑ Mehta, Aranyak (2013-10-16). "Online Matching and Ad Allocation". Foundations and Trends in Theoretical Computer Science. 8 (4): 265–368. doi:10.1561/0400000057. ISSN 1551-305X.
- ↑ Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007-10-01). "AdWords and generalized online matching". Journal of the ACM. 54 (5): 22–es. doi:10.1145/1284320.1284321. ISSN 0004-5411. S2CID 8481313.
- ↑ Buchbinder, Niv; Jain, Kamal; Naor, Joseph (Seffi) (2007), "Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue", Algorithms – ESA 2007, Lecture Notes in Computer Science, vol. 4698, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 253–264, doi:10.1007/978-3-540-75520-3_24, ISBN 978-3-540-75519-7 , retrieved 2020-09-03
- ↑ Andelman, Nir; Mansour, Yishay (2004). "Auctions with Budget Constraints". In Hagerup, Torben; Katajainen, Jyrki (eds.). Algorithm Theory - SWAT 2004. Lecture Notes in Computer Science. Vol. 3111. Berlin, Heidelberg: Springer. pp. 26–38. doi:10.1007/978-3-540-27810-8_4. ISBN 978-3-540-27810-8.
- ↑ Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris (2010-01-17), "Inapproximability for VCG-Based Combinatorial Auctions", Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 518–536, doi: 10.1137/1.9781611973075.45 , ISBN 978-0-89871-701-3
- ↑ Azar, Yossi; Birnbaum, Benjamin; Karlin, Anna R.; Mathieu, Claire; Nguyen, C. Thach (2008). "Improved Approximation Algorithms for Budgeted Allocations". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 5125. Berlin, Heidelberg: Springer. pp. 186–197. doi:10.1007/978-3-540-70575-8_16. ISBN 978-3-540-70575-8.
- ↑ Chakrabarty, Deeparnab; Goel, Gagan (2008-10-01). "On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 687–696. doi:10.1109/focs.2008.47. ISBN 978-0-7695-3436-7.
- ↑ Kalaitzis, Christos (2015-12-21). "An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 1048–1066. doi: 10.1137/1.9781611974331.ch74 . ISBN 978-1-61197-433-1.
- ↑ Srinivasan, Aravind (2008). "Budgeted Allocations in the Full-Information Setting". In Goel, Ashish; Jansen, Klaus; Rolim, José D. P.; Rubinfeld, Ronitt (eds.). Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 5171. Berlin, Heidelberg: Springer. pp. 247–253. doi:10.1007/978-3-540-85363-3_20. ISBN 978-3-540-85363-3.
- ↑ Devanur, Nikhil R.; Jain, Kamal; Sivan, Balasubramanian; Wilkens, Christopher A. (2019-01-12). "Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems". Journal of the ACM. 66 (1): 1–41. arXiv: 1903.03944 . doi:10.1145/3284177. ISSN 0004-5411. S2CID 59337566.
- ↑ Feldman, Michal; Gravin, Nick; Lucier, Brendan (2016-01-01). "Combinatorial Walrasian Equilibrium". SIAM Journal on Computing. 45 (1): 29–48. arXiv: 1304.2244 . doi:10.1137/13094339X. ISSN 0097-5397.
- ↑ Roughgarden, Tim; Talgam-Cohen, Inbal (2015-06-15). "Why Prices Need Algorithms". Proceedings of the Sixteenth ACM Conference on Economics and Computation. EC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 19–36. doi:10.1145/2764468.2764515. ISBN 978-1-4503-3410-5. S2CID 229372470.
- ↑ Garg, Jugal; Hoefer, Martin; Bei, Xiaohui; Mehlhorn, Kurt (2016). Computing equilibria in markets with budget-additive utilities. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 57. pp. 8:1–8:14. doi: 10.4230/LIPIcs.ESA.2016.8 . ISBN 9783959770156. S2CID 564953.
- ↑ Cole, Richard; Devanur, Nikhil; Gkatzelis, Vasilis; Jain, Kamal; Mai, Tung; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-20). "Convex Program Duality, Fisher Markets, and Nash Social Welfare". Proceedings of the 2017 ACM Conference on Economics and Computation. New York, NY, USA: ACM. pp. 459–460. arXiv: 1609.06654 . doi:10.1145/3033274.3085109. ISBN 978-1-4503-4527-9. S2CID 14525165.