- arXiv.org
- Data Analysis, Statistics and Probability
- Space Physics
- Popular Physics
- History and Philosophy of Physics
- Fluid Dynamics
- Optics
- Biological Physics
- Physics and Society
- General Physics
- Atomic and Molecular Clusters
- Atomic Physics
- Medical Physics
- Plasma Physics
- Geophysics
- Classical Physics
- Atmospheric and Oceanic Physics
- Chemical Physics
- Computational Physics
- Physics Education
- Instrumentation and Detectors
- Accelerator Physics

- Number Theory
- History and Overview
- Information Theory
- Statistics Theory
- Analysis of PDEs
- Mathematical Physics
- Complex Variables
- Representation Theory
- Algebraic Geometry
- Combinatorics
- Probability
- Metric Geometry
- Group Theory
- Symplectic Geometry
- Operator Algebras
- Numerical Analysis
- Optimization and Control
- Dynamical Systems
- Differential Geometry
- Geometric Topology
- Quantum Algebra
- Logic
- General Topology
- General Mathematics
- Classical Analysis and ODEs
- Algebraic Topology
- Rings and Algebras
- Commutative Algebra
- Functional Analysis
- Spectral Theory
- K-Theory and Homology
- Category Theory

- Computational Complexity
- General Literature
- Information Theory
- Multiagent Systems
- Information Retrieval
- Symbolic Computation
- Formal Languages and Automata Theory
- Emerging Technologies
- Computer Vision and Pattern Recognition
- Social and Information Networks
- Databases
- Learning
- Software Engineering
- Numerical Analysis
- Operating Systems
- Neural and Evolutionary Computing
- Programming Languages
- Other Computer Science
- Sound
- Digital Libraries
- Artificial Intelligence
- Human-Computer Interaction
- Cryptography and Security
- Mathematical Software
- Computational Engineering, Finance, and Science
- Hardware Architecture
- Systems and Control
- Distributed, Parallel, and Cluster Computing
- Discrete Mathematics
- Computer Science and Game Theory
- Performance
- Computation and Language
- Robotics
- Data Structures and Algorithms
- Networking and Internet Architecture
- Computational Geometry
- Logic in Computer Science
- Graphics
- Computers and Society
- Multimedia

- Apr 25 2017 cs.GT arXiv:1704.06901v1We study a class of procurement auctions, where an auctioneer is interested in buying resources or services from a set of agents. The auctioneer is interested in selecting a subset of agents so as to maximize her valuation function, without exceeding a given budget. As the resources are owned by strategic agents, our overall goal is to design mechanisms that are i) truthful, ii) budget-feasible, and iii) obtain a good approximation to the optimal value. Budget-feasibility creates more challenges, making several approaches inapplicable in this setting. Previous results on budget-feasible mechanisms have considered mostly monotone valuation functions. In this work, we mainly focus on symmetric submodular valuations, a prominent class of non-monotone submodular functions, that includes cut functions. We begin first with a purely algorithmic result, obtaining a $\frac{2e}{e-1}$-approximation for symmetric submodular functions under a budget constraint. We view this as a standalone result of independent interest, as it is the best known factor achieved by a deterministic algorithm. We then proceed to propose truthful, budget feasible mechanisms (both deterministic and randomized), paying particular attention on the Budgeted Max Cut problem. Our results significantly improve the known approximation ratios for these objectives, while establishing polynomial running time for many cases where only exponential mechanisms were known. For most symmetric submodular functions, only randomized mechanisms with very large approximation ratios were known prior to our results. At the heart of our approach lies an appropriate combination of local search algorithms with results for monotone submodular valuations, applied to the derived local optima.
- Apr 25 2017 cs.GT arXiv:1704.06828v1Recent initiatives by regulatory agencies to increase spectrum resources available for broadband access include rules for sharing spectrum with high-priority incumbents. We study a model in which wireless Service Providers (SPs) charge for access to their own exclusive-use (licensed) band along with access to an additional shared band. The total, or delivered price in each band is the announced price plus a congestion cost, which depends on the load, or total users normalized by the bandwidth. The shared band is intermittently available with some probability, due to incumbent activity, and when unavailable, any traffic carried on that band must be shifted to licensed bands. The SPs then compete for quantity of users. We show that the value of the shared band depends on the relative sizes of the SPs: large SPs with more bandwidth are better able to absorb the variability caused by intermittency than smaller SPs. However, as the amount of shared spectrum increases, the large SPs may not make use of it. In that scenario shared spectrum creates more value than splitting it among the SPs for exclusive use. We also show that fixing the average amount of available shared bandwidth, increasing the reliability of the band is preferable to increasing the bandwidth.

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of ...

Māris Ozols Oct 21 2016 21:06 UTCPiotr Migdał Apr 18 2014 18:43 UTC

...(continued)A podcast summarizing this paper, by Geoff Engelstein: [The Dice Tower # 351 - Dealing with the Mockers (43:55 - 50:36)](http://dicetower.coolstuffinc.com/tdt-351-dealing-with-the-mockers), and [an alternative link on the BoardGameGeek](http://boardgamegeek.com/boardgamepodcastepisode/117163/tdt-351